Основные понятия и методы теории формальных систем. Волохович А.В. - 16 стр.

      Запись ∃ х Р(х) будет означать, что существует предмет х области
V, обладающий свойством Р, или существует предмет х области V,
для которого Р(х) истинно.
      Пусть А – формула исчисления предикатов (определение формулы
будет дано далее) . В выражении ∀ х А (или ∃ х А) формула А
называется областью действия квантора ∀ х (соответственно ∃ х).
      Введем понятия свободного и связанного вхождения переменной в
формулу. Вхождение переменной х в данную формулу называется
связанным, если х является переменной входящего в эту формулу
квантора ∀ х (или ∃ х) или находится в области действия входящего в
эту формулу квантора ∀ х (или ∃ х); в противном случае вхождение
переменной х в данную формулу называется свободным. Отсюда
переменная называется свободной (связанной) переменной и данной
формуле, если существуют свободные (связанные) ее вхождения в
эту формулу.
      В общем случае ∀ x i ∀ x i … ∀ x i А(х 1 , х 2 , ..., х n ), где x i , x i , …, x i
                                1           2           r                    1       2   r


являются подмножеством переменных, х 1 , х 2 , ..., х n будет пониматься
как утверждение, что для любых значений, придаваемых
предметным переменным x i , x i , …, x i из области определения А(х 1 ,
                                            1   2           r


х 2 , ..., х n ), истинность А(х 1 , х 2 , ..., х n ) зависит только от свободных
переменных, входящих в эту формулу. Аналогично ∃ x i ∃ x i … ∃ x i       1       2       r


А(х 1 , х 2 , ..., х n ), где x i , x i , …, x i – также подмножество переменных,
                            1           2           r


х 1 , х 2 , ..., х n понимается как утверждение, что существуют значения
переменных x i , x i , …, x i из области определения А(х 1 , х 2 , ..., х n )
                   1   2            r


такие, что истинность А(х 1 , х 2 , ..., х n ) будет зависеть лишь от
свободных переменных, входящих в эту формулу.
      Если к формуле А(х 1 , х 2 , ..., х n ) применяем n раз какие-либо
кванторы, то получаем выражение, представляющее собой некоторое
постоянное высказывание, которое называется замкнутой формулой,
т. е. формулой без свободных переменных.
      Рассмотрим выражение ¬ ∀ x А(х), которое означает, что не для
всех х из области определения А(х) истинно. Это высказывание, в
свою очередь, равносильно высказыванию, что существует, по
крайней мере, один предмет х из области определения А(х), для
которого А(х) ложно, т. е. ¬ ∀ xА(х)= ∃ х ( ¬ А(х)).
      Аналогично можно показать, что ¬ ∃ xА(х)= ∀ х ( ¬ А(х)).
      Отсюда кванторы общности и существования называются
двойственными друг другу.
      Применяя правило силы операций, будем считать, что кванторы
∀ и ∃ располагаются по силе между связками ~, → и связками ∨ ,&, ¬ .
Во избежание недоразумений в ряде случаев будем ставить скобки.
      Таким образом, в исчислении предикатов используются:
      x 1 , x 2 , …, x n , … – предметные переменные;


16