A®B; B®C; C 2 страница. 4) применить закон дистрибутивности по переменной С:

4) применить закон дистрибутивности по переменной С:

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

5) ввести константу "и":

А&((АÚВ)&”и”Ú С&(АÚВ));

6) применить закон дистрибутивности для подформулы (АÚВ):

А&(АÚВ)&(“и”ÚС);

7) удалить (“и”ÚС):

А&(АÚВ);

8) применить закон поглощения:

А.

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

 

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

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

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

Б:= Борис решил все задачи;

Г:= Григорий решил все задачи;

Д:= Дмитрий решил все задачи;

Е:= Евгений решил все задачи;

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

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

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

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

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

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

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

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

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

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

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

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

Если допустить, что ùA=и и ùД=и, то первая формула может быть записана так:

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

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

Если допустить, что ùБ=и и ùЕ=и, то вторая формула может быть записана так:

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

т.к. члены Е&ùА=0 и Б&ùГ=0.

Если допустить, что ùЕ=и и ùА=и, то третья формула может быть записана так:

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

т.к. члены А&ùД=0, ùБ&Е=0, и ùС&А=0.

Если допустить, что ùБ=и и ùГ=и, то четвертая формула может быть записана так:

ùБ&ùГ&(ùА&ДÚА&ùД)&ùБ&Е&(ùЕ&АÚЕ&ùА)&(ùС&АÚС&ùА), т.к. член Б&ùЕ=0.

Если допустить, что ùС =и и ùА=и, то пятая формула может быть записана так:

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

т.к. член А&ùД=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₃));