Эквивалентные преобразования формул

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

Пример: F₁«F₂=(F₁®F₂)&(F₂®F₁)=(ùF₁ÚF₂)&(ùF₂ÚF₁)=ù(ù(ùF₁ÚF₂) Úù(ùF₂ÚF₁)).

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

F1

F2

F1«F2

F1®F2

F2®F1

4&5

ùF1ÚF2

ùF2ÚF1

7&8

ù7Úù8

ù10

Л

Л

И

И

И

И

И

И

И

Л

И

Л

И

Л

И

Л

Л

И

Л

Л

И

Л

И

Л

Л

Л

И

Л

Л

И

Л

И

Л

И

И

И

И

И

И

И

И

И

Л

И

 

Пример: Дано, F=(F₁®F₂)®((F₂®F₃)®(F₁ÚF₂®F₃)). Упростить формулу.

· Удалить всюду связку “®”:

F= ù(ùF₁ÚF₂)Ú(ù(ùF₂ÚF3)Ú(ù(F₁ÚF₂) ÚF₃);

· Опустить отрицание до элементарной формулы по закону де Моргана:

F=F₁&ùF₂ÚF₂&ùF₃ÚùF₁&ùF₂ÚF₃;

· Выполнить преобразование по закону дистрибутивности:

F=(F₁ÚùF₁) &ùF₂ÚF₂&ùF₃Ú F₃;

· Удалить член (F₁ÚùF₁), так как (F₁ÚùF₁)=и:

F=ùF₂ÚF₂&ùF₃Ú F₃;

· Выполнить преобразование по закону дистрибутивности:

F=ùF₂Ú(F₂ÚF3) &(ùF₃Ú F₃);

· Удалить член (F₃ÚùF₃)=и:

F=ùF₂Ú(F₂ÚF3);

· Применить закон ассоциативности:

F=(ùF₂ÚF₂)ÚF₃;

· Приравнять “истине” значение формулы F, т.к. (ùF₂ÚF₂)=и:

F=иÚF₃=и.

Следовательно, исходная формула при любых значениях пропозициональных переменных равна истине.

Пример: дано F=ù(F₁®F₂)&(ùF₃ÚùF₄)Úù(F₁ÚF₂)&ù(F₃&F₄).

Упростить выражение данной формулы.

· Удалить логическую связку “®”:

F=ù(ùF₁ÚF₂)&(ùF₃ÚùF₄)Úù(F₁ÚF₂)&ù(F₃&F₄);

· Опустить отрицание на элементарные формулы по закону де Моргана:

F=F₁&ùF₂&(ùF₃ÚùF₄)Ú ù F₁&ùF₂&(ùF₃ÚùF₄);

· Выполнить преобразование по закону дистрибутивности:

F=(F₁Úù F₁) &ùF₂&(ùF₃ÚùF₄);

· Удалить член (F₁ÚùF₁)=и:

F=ùF₂&(ùF₃ÚùF₄).

Следовательно, ù(F₁®F₂)&(ùF₃ÚùF₄)Úù(F₁ÚF₂)&ù(F₃&F₄)=ùF₂&(ùF₃ÚùF₄)

 

Пример: Дано суждение "или верно, что Петр поступил в университет (А), и при этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей поступил (В)" Кто же поступил в университет? [11].

Формула сложного высказывания имеет вид:

F=А&ù(ùA&ùВ)ÚА&СÚА&В&С;

· преобразовать, используя закон де Моргана:

F=А& (АÚВ)ÚА&СÚА&В&С;

· применить закон идемпотентности:

F=А& (АÚВ)ÚA&А&СÚА&В&С;

· применить закон дистрибутивности по переменной А:

F=А&((АÚВ)Ú А&СÚВ&С);

· применить закон дистрибутивности:

F=А&((АÚВ)Ú С&(АÚВ));

· применить закон дистрибутивности:

F=(АÚВ)&(АÚС);

Итак, А&ù(ùA&ùВ)ÚА&СÚА&В&С=(АÚВ)&(АÚС)=А.Ú(В&С).

Если в университет поступил только один из трех друзей, то

(В&С)=л. Следовательно, в университет поступил Петр.

Пример: Шесть школьников - Андрей, Борис, Григорий, Дмитрий, Евгений и Семен - участвовали в олимпиаде. Двое из них решили все задачи. На вопрос, кто решил все задачи, последовали ответы:1) Андрей и Дмитрий; 2) Борис и Евгений; 3) Евгений и Андрей; 4)Борис и Григорий; 5) Семен и Андрей. В четырех из этих ответов одна часть неверна, другая верна. В одном - обе части неверны. Кто же решил все задачи? [11]

Введем обозначения:

A:= Андрей решил все задачи, Б:= Борис решил все задачи,

Г:= Григорий решил все задачи, Д:= Дмитрий решил все задачи,

Е:= Евгений решил все задачи, С:= Семен решил все задачи.

Так как в одном из ответов обе части неверны, а в остальных - одна, то необходимо составить пять формул, отражающих пять различных высказываний:

ùA&ùД&(ùБ&ЕÚБ&ùЕ)&(ùЕ&АÚЕ&ùА)&(ùБ&ГÚБ&ùГ)&

(ùС&АÚС&ùА);

ùБ&ùЕ&(ùА&ДÚА&ùД) & (ùЕ&АÚЕ&ùА)&(ùБ&ГÚБ&ùГ)&

(ùС&АÚС&ùА);

ùЕ&ùА&(ùА&ДÚА&ùД)&(ùБ&ЕÚБ&ùЕ)&(ùБ&ГÚБ&ùГ)&

(ùС&АÚС&ùА);

ùБ&ùГ& (ùА&ДÚА&ùД)&(ùБ&ЕÚБ&ùЕ)&(ùЕ&АÚЕ&ùА)&

(ùС&АÚС&ùА);

ùС&ùА&(ùА&ДÚА&ùД)&(ùБ&ЕÚБ&ùЕ)&(ùЕ&АÚЕ&ùА)&

(ùБ&ГÚБ&ùГ).

Если ùA=и и ùД=и, то первая формула может быть записана так: ùA&ùД&(ùБ&ЕÚБ&ùЕ)&Е&ùА&(ùБ&ГÚБ&ùГ)&С&ùА, т.к. член ùЕ&А=л.

Если ùБ=и и ùЕ=и, то вторая формула может быть записана так: ùБ&ùЕ&(ùА&ДÚА&ùД)&ùЕ&А&ùБ&Г&(ùС&АÚС&ùА), т.к. члены Е&ùА=л и Б&ùГ=л.

Если ùЕ=и и ùА=и, то третья формула может быть записана так: ùЕ&ùА&ùА&Д&Б&ùЕ&(ùБ&ГÚБ&ùГ)&С&ùА, т.к. члены А&ùД=л, ùБ&Е=л, и ùС&А=л.

Если допустить, что ùБ=и и ùГ=и, то четвертая формула может быть записана так:ùБ&ùГ&(ùА&ДÚА&ùД)&ùБ&Е&(ùЕ&АÚЕ&ùА)&(ùС&АÚС&ùА), т.к. член Б&ùЕ=л.

Если ùС=и и ùА=и, то пятая формула может быть записана так:ùС&ùА&ùА&Д&(ùБ&ЕÚБ&ùЕ)& Е&ùА&(ùБ&ГÚБ&ùГ), т.к. член А&ùД=л.

Применив законы дистрибутивности, идемпотентности и поглощения эти формулы можно упростить так:

ùA&ùД&ùБ&Е&Г&С;

ùБ &ùЕ&ùД&ùС&А&Г;

ùЕ&ùА&ùГ&Д&С&Б;

ùБ&ùГ&ùА&Д&Е&С;

ùС&ùА&ùБ&Д&Е&Г.

По условиям задачи только два участника решили все задачи. Поэтому формулы, содержащие по три пропозициональных переменных без отрицания, не отвечают поставленным условиям, а одна, содержащая только две переменных без отрицания, отвечает условиям задачи. Это - ùБ&ùЕ&ùД&ùС&А&Г.

Следовательно, все задачи на олимпиаде решили Андрей (А) и Григорий (Г).

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

Нормальные формы формул

В алгебре высказываний используют две нормальные фор­мы: дизъюнктивную (ДНФ) и конъюнктивную нормальные формы формулы (КНФ).

ДНФ есть формула, равносильная формуле исходной логической функции и записанная в виде дизъюнкции элементарных конъюнкций, т.е.

F = K₁Ú K₂Ú K₃Ú.., где каждая K_i = (A&B&C&...).

В элементарной коньюнкции нет двух одинаковых пропозициональных переменных, т.к. F&F=F. А в ДНФ нет двух одинаковых элементарных коньюнкций, т.к. FÚF=F. Если одна из элементарных конъюнкций содержит (F&ùF), то следует удалить всю элементарную конъюнкцию, т.к.(F&ùF) = л.

 

Пример: если F=F₁&(F₂ÚùF₂)ÚF₂&(F₁ÚùF₁), то F=F₁&F₂ÚF₁&ùF₂ÚF₁&F₂ÚùF₁&F₂= F₁&F₂ÚF₁&ùF₂ÚùF₁&F₂.

Так сформирована ДНФ.

КНФ формулы есть формула, равносильная формуле исходной логической функции и записанная в виде конъюнкции элементарных дизъюнкций, построенных на пропозициональных переменных, т.е.

F = D₁& D₂& D₃&.., где каждая D_i = (AÚBÚCÚ...).

В элементарной дизьюнкции нет двух одинаковых пропозициональных переменных, т.к. FÚF=F. А в КНФ нет двух одинаковых элементарных дизьюнкций, т.к. F&F=F. Если одна из элементарных дизьюнкций содержит (FÚùF), то следует удалить всю элементарную дизъюнкцию, т.к.(FÚùF) = и.

Пример: если F=F₁&(F₁ÚF₂) ÚF₂&(F₁ÚùF₂), то

F=(F₁ÚF₂) &(F₁ÚùF₂).

Так сформирована КНФ.

Наибольшее распространение в логике высказываний по­лучили формулы вида КНФ, элементарные дизъюнкции которых D_i принято называть дизъюнктами, а члены каждого дизъюнкта A, B, C – атомами.

Исчисление высказываний

Исчисление высказываний следует начинать с определения множества аксиом и правил вывода, обеспечивающих доказательство истинности заключения. Доказательством или выводом называют конечную последовательность высказываний, каждое из которых является либо аксиомой, либо выводится из одного или нескольких предыдущих высказываний по правилам вывода.

Задание возможного числа аксиом определяет семантическую полноту исчисления, а задание правил использования аксиом и промежуточных высказываний в процессе формирования заключения – метод дедуктивного вывода.

Интерпретация формул

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

Все множество формул можно разбить на три класса: тождественно истинные, тождественно ложные и выводимые. В каждом классе множество формул перечислимо и счетное.

Тождественно истинные формулы – это особый класс формул, которые принимают значение “истины” при любом значении пропози­циональных переменных, входящих в эту формулу. Эти формулы играют роль аксиом и законов логики высказываний.

Например: F = ((A®B)&(A®C)®(A®(B&C))=и.

A	B	C	A®B	A®C	B&C	4&5	1®6	7®8
Л	Л	Л	И	И	Л	И	И	И
Л	Л	И	И	И	Л	И	И	И
Л	И	Л	И	И	Л	И	И	И
Л	И	И	И	И	И	И	И	И
И	Л	Л	Л	Л	Л	Л	Л	И
И	Л	И	Л	И	Л	Л	Л	И
И	И	Л	И	Л	Л	Л	Л	И
И	И	И	И	И	И	И	И	И

Тождественно ложные формулы - это особый класс формул, которые принимают значение “ложь” при любых значениях пропозициональных переменных, входящих в формулу.

Тождественно ложные формулы – это особый класс формул, которые принимают значение “лжи ” при любом значении пропози­циональных переменных, входящих в эту формулу.

Например, F=A&(ùBÚùC)&(A®B)&(A®C)=л.

 

A б) F = (A&(ùBÚùC)&(A®B)&(A®C)). A	B	C	ù2Úù3	1&4	1®2	1®3	5&6	8&7
Л	Л	Л	И	Л	И	И	Л	Л
Л	Л	И	И	Л	И	И	Л	Л
Л	И	Л	И	Л	И	И	Л	Л
Л	И	И	Л	Л	И	И	Л	Л
И	Л	Л	И	И	Л	Л	Л	Л
И	Л	И	И	И	Л	Л	Л	Л
И	И	Л	И	И	И	Л	И	Л
И	И	И	Л	Л	И	И	Л	Л

Выводимые формулы - это особый класс формул, которые принимают значения “истина” или “ложь” в зависимости от значений пропозициональных переменных.

Например, F=(ùА®C&ùВ)&(ùC®B&ùA)&(A®ùC).

 

A	B	C	3&ù2	ù1®4	2&ù1	ù3®6	1®ù3	5&7&8	Анализ таблицы показывает, что формула имеет значение “и” только при условии А=”л”, B=”л”, C=”и”.
Л	Л	Л	Л	Л	Л	Л	И	Л
Л	Л	И	И	И	Л	И	И	И
Л	И	Л	Л	Л	И	И	И	Л
Л	И	И	Л	Л	И	И	И	Л
И	Л	Л	Л	И	Л	Л	И	Л
И	Л	И	И	И	Л	И	Л	Л
И	И	Л	Л	И	Л	Л	И	Л
И	И	И	Л	И	Л	И	Л	Л

Недостаток использования таблиц истинности состоит в том, что при большом числе пропозициональных переменных процедура построения этих таблиц становится громоздкой, так как число строк таблицы равно 2n, а число столбцов не меньше (n+m), где n – число пропозициональных переменных, а m – число логических связок.

⇐ Предыдущая15161718192021222324Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: