Запись сложного высказывания в виде формулы логики высказываний
Если имеется несколько высказываний, то при помощи логических операций можно образовывать различные новые высказывания. При этом исходные высказывания принято называть простыми, а вновь образованные высказывания – сложными.
Пример 1.10.
Рассмотрим простые высказывания:.
A = "Будет холодное лето".
B = "Будет дождливое лето".
C = "Будет засушливое лето".
D = "Будет хороший урожай".
Формула (A&B Ú C) É ØD соответствует сложному высказыванию:
''Если будет холодное и дождливое или засушливое лето, урожай будет плохим".
Язык логики высказываний удобен для записи математических утверждений. Всякая теорема имеет вид импликации: А É B (прямая теорема); B É А (обратная теорема); ØB É ØА (противоположная теорема).
Пример 1.11.
A = “Треугольник прямоугольный”.
B = “Квадрат одной стороны равен сумме квадратов двух других сторон”
А É B (прямая теорема) = “Если треугольник прямоугольный, то квадрат одной стороны равен сумме квадратов двух других сторон”.
B É А (обратная теорема) = “Если квадрат одной стороны равен сумме квадратов двух других сторон, то треугольник прямоугольный”.
ØB É ØА (противоположная теорема) = “Если квадрат одной стороны не равен сумме квадратов двух других сторон, то треугольник не прямоугольный”.
В данном случае все три теоремы верны.
Равносильность А É B º ØB É ØА есть основание метода доказательства от противного. Например, для доказательства теоремы : “Если треугольник равнобедренный, то углы при основании равны” (А É B) достаточно доказать теорему: “Если углы при основании не равны, то треугольник не равнобедренный” (ØB É ØА).
Используя равносильные преобразования, можно получать различные формулировки одного и того же суждения, а также отрицаний суждений.
Пример 1.12.
Дано высказывание “Если политик обещает невыполнимое, то он обманывает людей”:
а) записать его в виде формулы логики высказываний;
б) произвести отрицание данного высказывания, так, чтобы результат не содержал внешних знаков отрицания; полученную при этом формулу записать на естественном языке.
Введем следующие высказывания:
A = ”Политик обещает невыполнимое”.
B = “Политик обманывает людей”.
Данное нам высказывание может быть записано в виде формулы: АÉB.
Построим отрицание высказывания, воспользовавшись равносильностью 12:
Ø(АÉB) ºA&ØB.
На естественном языке это может быть выражено следующим образом:
“Политик обещает невыполнимое, но он не обманывает людей”.
Нормальные формы
В алгебре высказываний используют две нормальные формы: дизъюнктивную и конъюнктивную нормальные формы формулы(ДНФ и КНФ).
ДНФ формулы есть формула, равносильная исходной формуле логики высказыванийи записанная в виде дизъюнкции элементарных конъюнкций переменных, т.е.
F = K1Ú K2Ú K3Ú . . ., где Ki = A&B&C& . . ..
КНФ формулы есть формула, равносильная исходной формуле логики высказываний и записанная в виде конъюнкции элементарных дизъюнкций переменных, т.е.
F = D1 & D2 & D3 & . . . , где Di = AÚBÚCÚ . . ..
Наибольшее распространение в логике высказываний получили формулы вида КНФ, элементарные дизъюнкции которых Di принято называть дизъюнктами, а члены каждого дизъюнкта A, B, C – атомами.
Пример 1.13.
Указать, в каких нормальных формах находятся следующие формулы логики высказываний.
a) A – ДНФ и КНФ
b) (AÚB)&C – КНФ
c) A Ú ØBÚ ØC – ДНФ и КНФ
d) (AÚB)&( ØAÚC) – КНФ
e) AÚB&C – ДНФ
f) A& ØB& ØC – ДНФ и КНФ
g) A&B Ú ØA&C – ДНФ
Для каждой формулы логики высказываний функции F имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).
Алгоритм приведения формул логики высказываний к ДНФ (КНФ).
Шаг 1. Все подформулы F вида A É B (т.е. содержащие импликацию) заменяем на ØAÚB или на Ø(A&ØB) (в соответствии с равносильностью 12 раздела 1.3).
Шаг 2. Все подформулы F вида A ~ B (т.е. содержащие эквивалентность) заменяем на (A&B) Ú (ØA&ØB) или на (AÚØB)&(ØAÚB) (в соответствии с равносильностью 13).
Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20).
Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).
Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18).
Шаг 6. Для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11.
Пример 1.14.
Дана формула F = Ø(A&B)&(AÚB).
Привести формулу к виду ДНФ:
1) F = (ØAÚØB)&(AÚB);
2) F = (ØA&A) Ú (ØA&B) Ú (ØB&A) Ú (ØB&B);
3) F = (ØA&B) Ú (ØB&A).
Пример 1.15.
Дана формула F = (A É (BÚØC)) É D.
Привести формулу к виду КНФ:
1) F = (ØAÚ(BÚØC)) ÉD ;
2) F = Ø(ØAÚ(BÚØC))ÚD ;
3) F = (A&(ØB)& C)ÚD ;
4) F = (AÚD)&(ØBÚD)&(CÚD).
Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).
Пример 1.16.
Указать, в каких нормальных формах находятся формулы логики высказываний трех переменных.
a) X&Y&Z – СДНФ и КНФ;
b) ØX&Y&Z Ú X&Y&ØZ – СДНФ;
c) XÚYÚZ – СКНФ и ДНФ;
d) X&Z – ДНФ и КНФ;
e) (ØXÚYÚZ)& (XÚYÚØZ) – СКНФ;
f) XÚYÚZ – СКНФ и ДНФ;
g) (XÚY)&(XÚØZ) – КНФ.
Каждая формула, не равная тождественно Л, может быть приведена к СДНФ, которая является единственной с точностью до перестановки дизъюнктивных членов.
Каждая формула, не равная тождественно И, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов.
Алгоритм приведения формулы булевой функции к СДНФ
Шаг 1. Используя алгоритм построения ДНФ, находим формулу F, являющуюся ДНФ данной формулы.
Шаг 2. Если в элементарную конъюнкцию Ki формулы F не входит ни переменная A, ни ее отрицание A, то на основании 1- го закона расщепления (равносильность 7а) заменяем Ki на (Ki & A ) Ú (Ki &ØA).
Шаг 3. В каждой элементарной конъюнкции переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, ..., n) на i-ом месте была либо переменная Ai, либо ее отрицание ØAi.
Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: Ki Ú Ki º Ki .
Пример 1.17.
F = A&ØBÚA&ØC&DÚA&B&C&ØD.
Преобразовать формулу к виду СДНФ:
1) F = A&ØB&CÚA&ØB&ØCÚA&B&ØC&DÚA&ØB&ØC&DÚ A&B&C&ØD;
2) F = (A&ØB&C&D)Ú(A&ØB&C&ØD)Ú(A&ØB&ØC&D)Ú(A&ØB&ØC&ØD)Ú (A&B&ØC&D)Ú (A&ØB&ØC&D)Ú (A&B&C&ØD).
Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на Ú и Ú на &.
Пример 1.18.
F = (AÚB)) &(ØAÚØBÚCÚD).
Преобразовать формулу к виду СКНФ:
1) F = (AÚBÚC) &(AÚBÚØC) &(ØAÚØBÚCÚD);
2) F = (AÚBÚCÚD)&(AÚBÚCÚØD)&(AÚBÚØCÚD) &(AÚBÚØCÚØD) &(ØAÚØBÚCÚD).
Совершенные нормальные формы удобно записывать, используя таблицы истинности, по значениям переменных и значению логической функции.
Алгоритм представления логической функции, заданной таблицей, формулой в СДНФ.
Шаг 1. Выбираем в таблице все наборы переменных A1, A2, ... , A n, для которых значение F равно И.
Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию переменных, причем в эту конъюнкцию переменная Ai записывается без изменений (т. е Ai), если ее значение равно “И” и со знаком отрицания (т. е ØAi), если ее значение равно “Л”.
Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.
Для получения формулы в СКНФ следует воспользоваться следующим алгоритмом.
Алгоритм представления логической функции, заданной таблицей, формулой в СКНФ
Шаг 1. Выбираем в таблице все наборы переменных A1, A2, ... , A n, для которых значение F равно Л
Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию переменных, причем в эту дизъюнкцию переменная Ai записывается без изменений (т. е Ai), если ее значение равно “Л” и со знаком отрицания (т. е ØAi), если ее значение равно “И”.
Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится формула данной функции в СКНФ.
Пример 1.19.
Записать СДНФ и СКНФ для функции, заданной таблицей истинности (таблица 1.6):
Таблица 1.6
А B C | F(A,B,C) |
Л Л Л Л Л И Л И Л Л И И И Л Л И Л И И И Л И И И | И Л Л И И Л Л И |
a) Формула СДНФ:
F(A,B,C) = ØА&ØB&ØC Ú ØА&B&ØC Ú А&ØB&ØC Ú А&B&C;
b) Формула СКНФ:
F(A,B,C) = (AÚBÚØC) &(AÚØBÚC) & (ØAÚBÚØC) &(ØAÚØBÚC).
Замечание. Т. к. всего строк в таблице функции 2n, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p+q=2n.
Так, для функции, рассмотренной в примере 1.19, n = 3, p = 4, q = 4, p + q = 8 = 23.