Приведенные и предваренные нормальные формулы

Формулы, в которых из логических символов имеются только символы Ù, Ú и Ø, причем символ Ø встречается лишь перед символами предикатов, называются приведенными формулами. Для каждой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают. Приведенная формула называется предваренной нормальной, если она не содержит символов кванторов или все символы кванторов стоят впереди. Для каждой приведенной формулы существует равносильная ей нормальная формула.

Пример 2.1.

Найти равносильную предваренную нормальную формулу для приведенной формулы: " x $ yA (x, y) Ù $ x $ u (x, u).

В формуле $ yA (x, y) переменная y связана, поэтому $ yA (x, y) не зависит от y. Обозначим D (x) = $ yA (x, y).

В формуле $ uB (x, u) переменная u связана, поэтому $ uB (x, u) не зависит от u. Обозначим F (x) = $ uB (x, u).

Тогда " x $ yA (x, y) Ù $ x $ uB (x, u) = " xD (x) Ù $ xF (x).

Применим правило переименования переменных и за скобки вынесем два квантора " x и $ x. Получим

" xD (x) Ù $ xF (x) º " x $ z (D (x) Ù F (z)).

Рассмотрим формулу D (x) Ù F (z) = $ yA (x, y) Ù $ uB (z, u). Применив два раза правило вынесения квантора за скобки, получим

$ yA (x, y) Ù $ uB (z, u) º $ y (A (x, y) Ù $ uB (z, u)) º $ y $ u (A (x, y) Ù B (z, u)).

Применив снова правило вынесения квантора за скобки, получим окончательно

" x $ yA (x, y) Ù $ x $ uB (x, u) º " x $ z $ y $ u (A (x, y) Ù B (z, u)).

В полученном тождестве в левой части – исходная формула, а в правой части – ее предваренная нормальная формула.

Пример 2.2.

Найти равносильную предваренную нормальную формулу для формулы: " x $ yA (x, y) ® $ x $ uB (x, u).

1. Найдем вначале приведенную формулу, равносильную данной. Избавимся от символа ®:

" x $ yA (x, y) ® $ x $ u (x, u) º Ø(" x $ yA (x, y)) Ú $ x $ uB (x, u).

Применим правило переноса квантора через отрицание:

Ø(" x $ yA (x, y)) º $ x " y Ø A (x, y),

Следовательно,

" x $ yA (x, y) ® $ x $ uB (x, u) º $ x " y Ø A (x, y)Ú $ x $ uB (x, u).

Правая часть тождества – приведенная формула, равносильная данной.

2. Найдем теперь предваренную нормальную формулу, равносильную приведенной формуле $ x " y Ø A (x, y) Ú $ x $ uB (x, u). Проделаем преобразование этой формулы аналогично предыдущему примеру:

$ x " y Ø A (x, y)Ú$ x $ uB (x, u) º $ x " y Ø A (x, y) Ú $ z $ uB (z, u) º

º " x $ z (" y Ø A (x, y) Ú $ uB (z, u)) º " x $ z " y $ u (Ø A (x, y) Ú B (z, u)).

Получена предваренная нормальная формула, равносильная исходной.

 

Выражение суждения в виде формулы логики предикатов

Суждение – это мысль, в которой утверждается наличие или отсутствие свойств предметов, отношений между предметами. Простым суждением называется суждение, в котором нельзя выделить часть, в свою очередь являющуюся суждением. Среди простых суждений выделяют атрибутивные суждения и суждения об отношениях. В атрибутивных суждениях выражается наличие или отсутствие у предметов некоторых свойств. Например, "Иванов – спортсмен", "некоторые моря имеют пресную воду".

Все атрибутивные суждения можно разделить на типы и перевести на язык логики предикатов: " a есть P " – P (a); "Все S есть P " – " x (S (x)® P (x)) (общеутвердительное суждение); "Ни один S не есть P " – " x (S (x)®Ø P (x)) (общеотрицательное суждение); "Некоторые S есть P " – $ x (S (x)Ù P (x)); (частноутвердительное суждение); "Некоторые S не есть P "– $ x (A (x)ÙØ P (x)) (частноотрицательное суждение).

При переводе на язык логики предикатов надо руководствоваться правилом: если кванторная переменная связана квантором общности ("), то в формуле используется знак импликации (®), а если кванторная переменная связана квантором существования ($), то в формуле используется знак конъюнкции (Ù).

Пример 2.3.

Перевести на язык логики предикатов следующие суждения.

а) Андрей – студент.

Заменим имя " Андрей" символом " а " и введем предикат P (x) = " x – студент". Это суждение можно выразить формулой: P (а).

б) Всякая логическая функция может быть задана таблицей.

Введем предикаты S (x) = " x – логическая функция"; P (x) = " x может быть задана таблицей". Это суждение можно выразить формулой: " x (S (x) ® P (x)).

в) Ни один человек не всеведущ.

Введем предикаты S (x) = " x – человек"; P (x) = " x всеведущ". Суждение можно выразить формулой: " x (S (x) ® Ø P (x)).

г) Некоторые студенты были на конференции.

Введем предикаты S (x) = " x – студент"; P (x) = " x был на конференции". Суждение можно выразить формулой: $ x (S (x) Ù P (x)).

д) Некоторые люди не умеют слушать.

Введем предикаты S (x) = " x – человек"; P (x) = " x умеет слушать". Суждение можно выразить формулой: $ x (A (x) Ù Ø P (x)).

Суждения об отношениях выражают отношения между объектами. При переводе этих суждений в формулы используют многоместные предикаты и рассмотренные правила. При переводе отрицаний суждений на язык формул применяется правило переноса квантора через знак отрицания и другие равносильные преобразования.

Пример 2.4.

Суждение "Некоторые студенты сдали все экзамены" записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык.

Введем предикаты: A (x) = " x – студент"; B (y) = " y – экзамен", C (x, y) =
" x сдал экзамен y ". Тогда предложение "Некоторые студенты сдали все экзамены" можно записать в виде следующей формулы:

$ x " y (A (x)Ù B (y) ® C (x, y)).

Построим отрицание этой формулы, применяя равносильные преобразования:

Ø$ x " y (A (x)Ù B (y)® C (x, y))) º " x $ y (Ø(A (x)Ù B (y) ® C (x, y))º

º " x $ y (A (x)Ù B (y)Ù Ø C (x, y)).

Это предложение можно прочитать следующим образом:

"Каждый студент не сдал хотя бы один экзамен".

 

Задания

1. Данную формулу логики предикатов привести к предваренной нормальной форме.

2. Данное суждение записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык.

 

Варианты индивидуальных заданий

Вариант № 1

1. " x (P (x)Ù R (x)®$ yQ (x,y)).

2. Не всякое действительное число является рациональным.

Вариант № 2

1. " x (P (x)®(R (x)((yQ (x,y)).

2. Каждый студент выполнил хотя бы одну практическую работу.

Вариант № 3

1. " xP (x)®$ yP (y))Ú" z $x R (x, z).

2. Ни одно четное число, большее 2, не является простым.

Вариант № 4

1. " x ($ y (Ø P (x)Ù Q (y))® R (y, z)).

2. Некоторые звезды не видны.

Вариант № 5

1. " x ($ y (Ø P (x, y)Ù Q (y, z))).

2. Произведение любых двух простых чисел не является простым числом.

Вариант № 6

1. " x ($ y (Ø P (x))Ù Q (y)).

2. Всякое положительное число больше всякого отрицательного числа.

Вариант № 7

1. " x ($ y (Ø P (x))«Q (y, z)).

2. Все ромбы являются параллелограммами.

Вариант № 8

1. " x (P (x) ® Q (x, y)) ® ($yP(y) ® $ z Q(y, z)).

2. Некоторые четные функции периодические.

Вариант № 9

1. $ x P(x, y)® (Q (x) ® Ø$ u (P (x, u))).

2. Всякий равносторонний треугольник является равнобедренным.

Вариант № 10

1. " x " y ($ zP (x, z) Ù Q (x, z)) ® $ uR (x, y, u).

2. Некоторые змеи ядовиты.

Вариант № 11

1. " x (P (x) ® $ y (Q (x, y) Ú $ zR (x, y, z))).

2. Некоторые реки не судоходны.

Вариант № 12

1. " x (P (x) «$ yQ (x, y).

2. Никакое знание не бесполезно.

Вариант № 13

1. Ø($ x " yP (x, y)Ú (" x " y $ zQ (x, y, z)))Ù$ yR (y).

2. Некоторые абитуриенты поступили в институт.

Вариант № 14

1. " x (P (x) ® Ø($ y " zQ (x, y, z))).

2. Студент ответил на некоторые вопросы.

Вариант № 15

1. ((Ø$ xP (x)) Ú (" xQ (x))Ù(R (x) ®" yS (x, y)).

2. Автобус останавливается на всех остановках.

Вариант № 16

1." x P (x) «$ xQ (x).

2. Ни одна монотонная функция не явлвется четной.

Вариант № 17

1. (Ø" xP (x) Ú $ xQ (x))Ù(R ®$ S (x, y)).

2. Ни один лентяй не заслуживает похвалы.

Вариант № 18

1. P (x, y) ® Ø($ xQ (x, y)Ú" uP (u)).

2. Не все металлы твердые.

Вариант № 19

1. " x " y (Q (x) «Ø(P (x, y)ÚØ($ uR (x, y, u)))).

2. Некоторые студенты получают стипендию.

Вариант № 20

1. Ø P (x, y) «(" xQ (x)ÙØ($ y " uR (y, u, y))).

2. Некоторые параллелограммы являются ромбами.

 

Тема 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ