Свойства логического следствия

1. Если А|=B, то |=A–›B.

2. А₁, А₂ ,…, A_n|=B тогда и только тогда, когда А₁, А₂,…, A_n-1 |= A_n –› В.

3. А₁, А₂ ,…, A_n|=B тогда и только тогда, когда |=(А₁^А₂^….^A_n) –›В.

4. Логическим следствием совокупности формул является любая формула этой совокупности А₁, А₂, …, A_n |=A_i, i=1,…, n.

5. Если А₁, А₂,…, A_n |=В_i, i=1,…, n, и В₁, В₂, …, В_k |=C, то А₁, А₂, …, A_n |=С.

 

 

Равносильность формул

Формулы А и В называются равносильными, если на любом наборе значений переменных они принимают одинаковые истинностные значения. АºВ.

Пример: X–›Yº⌐XÚ Y

Доказательство:

X	Y	X–›Y	⌐X	⌐XÚY
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
0	0	1	1	1

 

Свойства равносильных формул

1) АºВ тогда и только тогда, когда А‹–›В

2) АºА

АºВ следует ВºА

АºВ, ВºС следует АºС

3) Свойства подстановки

Если АºВ, то для любых формул F(x1,…xn) верно следующая равносильность

F(x1,….., A,…,xn) ºF(x1,…., B,…xn)

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

Утверждение 1. Система логических связок S={^,Ú,⌐} полная.

Утверждение 2. Система логических связок S={Ú,⌐} полная.

Утверждение 3. Система логических связок S={^,⌐} полная.

 

Нормальные формы формул алгебры высказываний.

Применения алгебры высказываний.

Конъюнктивным одночленом от переменных x₁, x₂, …, x_n называется конъюнкция этих переменных или их отрицаний (x₁^x₂^⌐x₁).

Дизъюнктивным одночленом от переменных x₁, x₂, …, x_n называется дизъюнкция этих переменных или их отрицаний (⌐x₁ Ú⌐x₂ Úx₁).

Конъюнктивной нормальной формой (КНФ). Формулы алгебры высказываний называется конъюнкция дизъюнктивных одночленов (⌐x₁ Ú⌐x₂)^(⌐x₁ Ú x₁).

Дизъюнктивной нормальной формой (ДНФ). Формулы алгебры высказываний называется дизъюнкция конъюнктивных одночленов (x₁ ^x₂) Ú (⌐x₁ ^ x₂).

Совершенным конъюнктивным (СК) одночленом от переменных x₁, x₂, …, x_n - называется конъюнкция всех этих переменных либо их отрицаний.

Совершенным дизъюнктивным (СД) одночленом от переменных x₁, x₂, …, x_n - называется дизъюнкция всех этих переменных либо их отрицаний.

СКНФ (СДНФ) называется конъюнкция (дизъюнкция) совершенных дизъюнктивных (конъюнктивных) одночленов.

Теорема о существовании СД одночлена.

Для каждого набора α=(α₁, α₂, …, α_n) значений переменных x₁, x₂, …, x_n существует и притом единственный СД одночлен, принимающий значение ложь на этом наборе.

Теорема о существовании СК одночлена.

Для каждого набора α=(α₁, α₂, …, α_n) значений переменных x₁, x₂, …, x_n существует и притом единственный СК одночлен, принимающий значение истина на этом наборе.

Теорема о существовании СДНФ.

Для любой не тождественно ложной формулы алгебры высказываний существует равносильная ей СДНФ и притом единственная с точностью до перестановки СК одночленов.

Теорема о существовании СКНФ.

Для любой не тождественно истинной формулы алгебры высказываний существует равносильная ей СКНФ и притом единственная с точностью до перестановки СД одночленов.

Применение совершенных форм.

Нахождение всех возможных следствий из данных посылок.

Теорема: Любая не тождественно истинная формула F(x₁, x₂, …, x_n), является логическим следствием совокупности формул А₁(x₁, x₂, …, x_n), …, А_k(x₁, x₂, …, x_n), не все из которых являются тождественно истинными, тогда и только тогда, когда все СД одночлены входящие в СКНФ формулы F входят в СКНФ формулы А₁^А₂^…..^A_k.

Нахождение посылок для данного следствия.

Теорема: (алгоритм получения посылок)

Для того чтобы найти все возможные формулы, из каждой из которых логически следует не тождественная формула G(x₁, x₂, …, x_n), необходимо:

1. Составить СКНФ для формулы G.

2. Выписать все дизъюнктивные одночлены, отсутствующие в СКНФ формулы G.

3. Составить все возможные конъюнкции формулы G с отсутствующими СД одночленами.

Все получившиеся формулы являются посылками для формулы G.

Обоснование метода доказательства от противного.

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

Свойства:

1. Совокупность формул противоречивая тогда и только тогда, когда логическим следствием этой совокупности является противоречие.

2. А1, А2, …, An противоречива тогда и только тогда, когда |=⌐(А1^А2^….^An)

Теорема.

Если логическим следствием совокупности формул А1,А2,….Ak,⌐B- противоречивая совокупность формул, то логическим следствием совокупности А1,А2,….Ak|=B является формула В.