Отрицание конъюнкция дизъюнкция импликация эквивалентность

 

A	7A		A	B	AÙB	AÚB	A®B	A«B

 

Значение составного высказывания вычисляется по логическим значениям содержащихся в нем элементарных высказываний в соответствии с определениями логических операций.

 

l(7A)= 7l(A),

l (A₁*A₂) = l (A₁)*l (A₂),

где * – один из символов Ù, Ú, ®, «

ОК АВ 2

Пропозициональные переменные – переменные,

принимающие значения на множестве высказываний.

 

X, Y, Z, …, X₁, X₂, X₃, …

 

Опр. 1) Всякая пропозициональная переменная есть формула АВ.

2) Если F₁, F₂ – формулы АВ, то 7F₁, (F₁*F₂), где * – один из символов Ù,

Ú, ®, «, являются формулами АВ.

3) Других формул АВ нет.

 

Если F(X₁, X₂, …, X_n) – формула АВ и A₁, A₂, …, A_n – некоторые высказывания,

то F(A₁, A₂, …, A_n) называется конкретизацией F на наборе A₁, A₂, …, A_n.

 

Значение F на наборе A₁, A₂, …, A_n – l(F(A₁, A₂, …, A_n)).

 

Бесконечному множеству конкретизаций формулы F соответствует

конечное множество их логических значений.

 

Таблица истинности формулы F(X1, X2, …, Xn) содержит 2n строк	X1	X2	…	Xn-1	Xn	F(X1, X2, …, Xn)
		...			F(0, 0,..., 0, 0)
		...			F(0, 0,..., 0, 1)
	...	...	...			F(0, 0,..., 1, 0)
Наборы нулей и единиц располагаются в лексикографическом порядке			...			...
		...	...	...	...
		...			...
		...			...
	...	...	...	...	...	...
			...			F(1, 1,..., 1, 0)
			...			F(1, 1,..., 1, 1)

 

 

ОК АВ 3

 

Классификация формул АВ

 

Формула АВ

 

Выполнимая тавтология опровержимая противоречие

╞ F F╞

Существует истинная конкретизация

Любая конкретизация истинна

Существует ложная конкретизация

Всякая конкретизация ложна

 

Основные тавтологии АВ

 

1) XÚ7X (закон исключенного третьего)

2) 7(XÙ7X) (закон отрицания противоречия)

3) ((X®Y)ÙX)®Y (modus ponens)

4) (X®Y)«(7Y®7X) (закон контрапозиции)

5) (X®(Y®Z))«(Y®(X®Z)) (правило перестановки посылок)

6) ((X®Y)Ù(Y®Z))®(X®Z) (закон силлогизма)

 

Доказательство: 1 способ – табличный; 2 способ – рассуждениями.

 

5) Предположим, что формула (X®(Y®Z))«(Y®(X®Z)) не является тавтологией Þ

существуют значения X,Y,Z такие, что она обращается в ложное высказывание Þ Þ Þ Þ

Þ Þ ни одна из систем совокупности не имеет решения Þ предположение было неверным Þ

формула (X®(Y®Z))«(Y®(X®Z)) является тавтологией.

 

 

ОК АВ 4

 

Формула H(X₁, X₂, …, X_n) называется логическим следствием

формулы F(X₁, X₂, …, X_n), если конкретизация H истинна всякий раз,

как только истинна соответствующая конкретизация формулы F

 

F╞ H Û [для всех A₁, A₂, …, A_n l(F(A₁, A₂, …, A_n))=1 Þ l(H(A₁, A₂, …, A_n))=1]

опр

 

Признак логического следствия: F╞ H Û ╞ F ®H

(Доказательство методом от противного на основе определений)

 

Формула H(X₁, X₂, …, X_n) называется логическим следствием

формул F₁(X₁, X₂, …, X_n), F₂(X₁, X₂, …, X_n),..., F_m(X₁, X₂, …, X_n),если конкретизация H истинна всякий раз, как только истинны соответствующие конкретизации формул F₁, F₂,..., F_m.

 

F₁, F₂,..., F_m ╞ H

 

Т. Следующие утверждения эквивалентны:

1) F₁, F₂,..., F_m ╞ H

2) F₁Ù F₂Ù... ÙF_m ╞ H

3) ╞ (F₁Ù F₂Ù... ÙF_m) ® H

4) F₁Ù F₂Ù... ÙF_mÙ7H ╞

 

Доказательство: 1) Þ 2) Þ 3) Þ 4) Þ 1)

 

Докажем 4) Þ 1): Пусть F₁Ù F₂Ù... ÙF_mÙ7H является противоречием и при этом неверно, что F₁, F₂,..., F_m ╞ H Þ существует набор конкретных высказываний (A₁, A₂, …, A_n) такой, что l(H(A₁, A₂, …, A_n))=0 в то время, как l(F₁(A₁, A₂, …, A_n)) = l(F₂(A₁, A₂, …, A_n)) =…= l(F_m(A₁, A₂, …, A_n)) = 1 Þ существует набор конкретных высказываний (A₁, A₂, …, A_n) такой, что l(7H(A₁, A₂, …, A_n)) = 1 в то время, как l(F₁(A₁, A₂, …, A_n))=l(F₂(A₁, A₂, …, A_n)) =…= l(F_m(A₁, A₂, …, A_n)) =1 Þ на некотором наборе конкретных высказываний l((F₁Ù F₂Ù... ÙF_mÙ7H) (A₁, A₂, …, A_n))=1 Þ

Þ F₁Ù F₂Ù... ÙF_mÙ7H не является противоречием

Пришли к отрицанию условия 4), значит, предположение было неверным, т. е. [ F₁Ù F₂Ù... ÙF_mÙ7H ╞ ] Þ [ F₁, F₂,..., F_m ╞ H ].

Остальные случаи доказываются аналогичным образом.

 

Ответить на вопрос, имеет ли место логическое следование F₁, F₂,..., F_m ╞ H, можно:

1) с помощью таблиц истинности формул F₁, F₂,..., F_m, H, проверяя выполнение требований определения;

2) с помощью рассуждений методом от противного.

ОК АВ 5

Формулы F(X₁, X₂, …, X_n) и H(X₁, X₂, …, X_n) называются

логически равносильными,

если логические значения их конкретизаций совпадают на любом наборе

конкретных высказываний A₁, A₂, …, A_n

 

F@H Û [на любом наборе A₁, A₂, …, A_n l(F(A₁, A₂, …, A_n))=l(H(A₁, A₂, …, A_n))]

опр

Признак логической равносильности: F@ H Û ╞ F «H

(Доказательство на основе определений)

 

Т. F@ H Û F╞ H и H╞ F