A®B; B®C; C 2 страница

т.к. член А&ùД=0.

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

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

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

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

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

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

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

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

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

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

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₂).

1) по закону дистрибутивности:

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

2) по законам идемпотентности и противоречия:

F=F₁ÚF₁&F₂;

3) по закону поглощения:

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₂).

1) по закону дистрибутивности:

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

2) по закону дистрибутивности:

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

3) по закону идемпотентности и исключенного третьего:

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

4) по закону идемпотентности:

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

5) по закону дистрибутивности:

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

6) по закону противоречия:

F=F₁.

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

1.1.5.1 Алгоритм приведения к нормальной форме

Шаг 1. Устранить логические связки “«” и “®” всюду по правилам:

F₁ «F₂ =(F₁®F₂)&(F₂®F₁)=(ù F₁Ú F₂)&(ù F₂Ú F₁)=(ù F₁&ù F₂)Ú(F₁& F₂);

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

Шаг 2. Продвинуть отрицание до элементарной формулы (пропозициональной переменной) по правилам:

ù(ù F) = F;

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

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

Шаг 3. Применить закон дистрибутивности:

a) для КНФ: F₁Ú(F₂ &F₃) = (F₁Ú F₂)&(F₁ÚF₃);

b) для ДНФ: F₁&(F₂Ú F₃) = (F₁&F₂)Ú(F₁&F₃).

 

Пример: Дана формула F=((F₁®(F₂ÚùF₃))®F₄).

Привести формулу к виду КНФ:

1) F=(ùF₁Ú(F₂Úù F₃))®F₄;

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

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

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

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

 

Пример: Дана формула F=(ù(F₁&F₂)&(F₁ÚF₂)).

Привести формулу к виду ДНФ:

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

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

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

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

Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).

 

1.1.5.2 Алгоритм преобразования ДНФ к виду СДНФ.

Шаг 1: если в элементарную конъюнкцию F не входит подформула F_i или ùF_i, то дополнить элементарную конъюнкцию высказыванием (F_iÚùF_i) и выполнить преобразование формулы по закону дистрибутивности:

F&(F_iÚùF_i)= F&F_iÚF&ùF_i;

Шаг 2: если в элементарную конъюнкцию F не входит подформула F_j или ùF_j, то повторить шаг 1, иначе – конец.

 

Пример: Дано F=F₁&ùF₂ÚF₁&ùF₃&F₄ÚF₁&F₂&F₃&ùF₄.

Преобразовать формулу к виду СДНФ:

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

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

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

4) 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₄).

 

1.1.5.3 Алгоритм преобразования КНФ к виду СКНФ.

Шаг 1: если в элементарную дизьюнкцию F не входит подформула F_i или ùF_i, то дополнить элементарную дизьюнкцию высказыванием (F_i&ùF_i) и выполнить преобразование формулы по закону дистрибутивности:

FÚ(F_i &ùF_i) = (FÚ F_i)&(FÚùFi);

Шаг 2: если в элементарную конъюнкцию F не входит подформула F_j или ùF_j, то повторить шаг 1, иначе – конец.

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

Преобразовать формулу к виду СКНФ:

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

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

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

4) F=(F₁ÚF2ÚF₃ÚF4)&(F₁ÚF2ÚF₃ÚùF4)&(F₁ÚF₂ÚùF₃ÚF4) &(F₁ÚF₂ÚùF₃ÚùF4) &(ùF₁ÚùF₂ÚF₃ÚF₄).

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

Элементарные коньюнкции СДНФ формируются для значений формулы “и”. Число элементарных коньюнкций равно числу истинных значений формулы. Пропозициональные переменные, входящие в элементарную коньюнкцию, записываются без изменений, если их значение равно “и” и с логической связкой “ù”, если их значение равно “л”.

Элементарные дизьюнкции СКНФ формируются для значений формулы “л”. Число элементарных дизьюнкций равно числу ложных значений формулы. Пропозициональные переменные, входящие в элементарную дизьюнкцию, записываются без изменений, если их значение равно “л” и с логической связкой “ù”, если их значение равно “и”.

A 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).

 

 

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

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

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

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

 

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

Если дана некоторая формула F и каждой ее пропозициональной переменной приписано значение "и" или "л", то говорят что дана интерпретация формулы F.

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

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

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

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

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

Пример: Определить, к какому классу относятся формулы:

a) F = ((A®B)&(A®C)®(A®(B&C))

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

 

Формула принадлежит классу тож­дественно истинных формул (см. столбец 9).

б) F=A& (ùBÚùC) &(A®B) & (A®C)

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

 

Формула принадлежит классу тождественно ложных формул (см. столбец 9).

 

в) F = (AÚB)&(B®ùC).

Формула принимает значение “и” или “л” для различных наборов значений   A	B	C	1Ú2	2®ù3	4&5
Л	Л	Л	Л	И	Л
Л	Л	И	Л	И	Л
Л	И	Л	И	И	И
Л	И	И	И	Л	Л
И	Л	Л	И	И	И
И	Л	И	И	И	И
И	И	Л	И	И	И
И	И	И	И	Л	Л

 

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

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

Пример: В семье есть договоренность относительно пользования телевизором на субботние вечера: а) если не смотрит отец(ùА), то смотрит дочь (C) и не смотрит мать (ùВ), т.е. F₁=(ùА®C&ùВ);б) если не смотрит дочь (ùC), то смотрит мать (В) и не смотрит отец (ùА), т.е. F₂=(ùC®B&ùA); в) если смотрит отец (A), то не смотрит дочь (ùC), т.е. F₃=(A®ùC). В каком случае совместимы эти условия? [2]

Формальная запись этого суждения имеет вид:

F=F₁&F₂&F₃=(ùА®C&ùВ)&(ùC®B&ùA)&(A®ùC).

 

Анализ таблицы показывает (см. столбец 9), что эти условия совместимы (см. строку 2), когда А=л, В=л и С=и (см. строку 2).   A	B	C	3&ù2	ù1®4	2&ù1	ù3®6	1®ù3	5&7&8
Л	Л	Л	Л	Л	Л	Л	И	Л
Л	Л	И	И	И	Л	И	И	И
Л	И	Л	Л	Л	И	И	И	Л
Л	И	И	Л	Л	И	И	И	Л
И	Л	Л	Л	И	Л	Л	И	Л
И	Л	И	И	И	Л	И	Л	Л
И	И	Л	Л	И	Л	Л	И	Л
И	И	И	Л	И	Л	И	Л	Л

 

 

1.2.2 Аксиомы исчисления высказываний

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

Ниже приведена одна из систем аксиом:

А1. F₁®(F₂®F₁);

А2. (F₁®F₂)®((F₂®F₃))®(F₁®F₃));

А3. (F₁& F₂)®F₁;

А4. (F₁& F₂)®F₂;

А5. F₁®(F₂®(F₁&F₂));

А6. F₁®(F₁ÚF₂);

А7. F₂®(F₁ÚF₂);

А8. (F₁®F₃)®((F₂®F₃)®((F₁ÚF₂)®F₃));

А9. (F₁®F₂)®((F₁®ù F₂)®ù F₁);

A10. (F₁®F₂)®((F₁&F₃)®(F₂&F₃));

A11. (F₁® F₂)®((F₁ÚF₃)®(F₂ÚF₃));

А12. ùù F₁ ® F₁.

 

Для проверки тождественной истинности аксиом рассмотрим таблицы истинности для A2 и A8:

 

А2. (F₁® F₂)®((F₁®(F₂® F₃))®(F₁® F₃))

 

F1	F2	F3	1®2	1®3	2®3	1®6	7®5	4®8
л	л	л	и	и	и	и	и	и
л	л	и	и	и	и	и	и	и
л	и	л	и	и	л	и	и	и
л	и	и	и	и	и	и	и	и
и	л	л	л	л	и	и	л	и
и	л	и	л	и	и	и	и	и
и	и	л	и	л	л	л	и	и
и	и	и	и	и	и	и	и	и

 

А8. (F₁® F₃)®((F₂ ® F₃)®((F₁ Ú F₂)® F₃))

 

F1	F2	F3	1Ú 2	1®3	2®3	4®3	6®7	5®8
л	л	л	л	и	и	и	и	и
л	л	и	л	и	и	и	и	и
л	и	л	и	и	л	л	и	и
л	и	и	и	и	и	и	и	и
и	л	л	и	л	и	л	л	и
и	л	и	и	и	и	и	и	и
и	и	л	и	л	л	л	и	и
и	и	и	и	и	и	и	и	и

.

 

1.2.3 Правила вывода

Выводом формулы В из множества формул F ₁; F ₂;... F _n называется такая последовательность формул, что любая F _i есть либо аксиома, либо непосредственно выводима из подмножества предшествующих ей формул F ₁; F ₂;... F _n.

В этом случае формулу B называют заключением, а последовательность формул F ₁; F₂;... F _n, сформированная отношением логического вывода, представляет схему дедуктивного вывода.