Файл: В. Ф. Пономарев математическая логика.doc

Сравните значения логических функций в третьем, шестом, девятом и одиннадцатом столбцах. То есть исполнение операции эквиваленции всегда можно заместить исполнением операций импликации и конъюнкции или дизьюнкции и отрицания.
Пример: F₁F₂ = F₁F₂F₁F₂= ((F₁F₂)(F₁F₂)).




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

---

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

Если формула F содержит подформулу F_i, то замена подформулы F_i в формуле F на эквивалент­ную ей формулу F_j не изменяет значения формулы F при любом наборе пропозициональных переменных. Если необходима подстановка в формулу F вместо формулы F_i новой формулы F_j , то эту операцию нужно выполнить всюду по символу F_i .

Правила замены и подстановки расширяют возможности эквива­лентных преобразований формул сложных высказываний.
Пример: Дано F=(F₁F₂) ((F₂F₃) (F₁F₂ F₃).

Выполнить преобразования для упрощения алгебраического выражения.

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

F= (F₁F₂)(( F₂F3)((F₁F₂) F₃);

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

F=F₁F₂F₂F₃F₁F₂F₃;

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

F=( F₁F₁) F₂F₂F₃ F₃;

4. 
   Удалить член ( F₁F₁), так как ( F₁F₁)=и:
   

F=F₂F₂F₃ F₃;

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

F=F₂(F₂F3) (F₃ F₃);

6. 
   Удалить член ( F₃F₃)=и:
   

F=F₂(F₂F3);

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

F=(F₂F₂)F₃;

7. 
   Приравнять “истине” значение формулы 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₃F₄)  F₁F₂(F₃F₄);

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

F=( F₁ F₁

---

) F₂(F₃F₄);

4) Удалить член ( F₁F₁)=и:

F=F₂(F₃F₄).

Дальнейшее упрощение формулы F невозможно.
Пример: Дано суждение "или верно, что Петр поступил в университет (А), и при этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей поступил (В)"[2].

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

А(AВ)АСАВС;

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

А (АВ)АСАВС;

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

А (АВ)AАСАВС;

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

А((АВ) АСВС);

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

---