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

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