Курс высшей математики (стр. 9 )

Пример. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.

Составим таблицы истинности для каждой формулы:

p	r		(pÙr)
И	И	Л	И	И
И	Л	Л	Л	И
Л	И	И	Л	Л
Л	Л	И	Л	Л

p	r
И	И	Л	Л	Л	И
И	Л	Л	И	И	И
Л	И	И	Л	И	И
Л	Л	И	И	И	И

Данные формулы не являются эквивалентными.

Пример. С помощью таблиц истинности проверить, являются ли эквивалентными формулы j и y.

Составим таблицы истинности для заданных формул.

p	q	r	pÛq	(pÛq)Úr
И	И	И	И	И
И	И	Л	И	И
И	Л	И	Л	И
И	Л	Л	Л	Л
Л	И	И	Л	И
Л	И	Л	Л	Л
Л	Л	И	И	И
Л	Л	Л	И	И

p	q	r	pÞq	qÞp	(pÞq)Ú(qÞp)	(pÞq)Ú(qÞp)Úr
И	И	И	И	И	И	И
И	И	Л	И	И	И	И
И	Л	И	Л	И	И	И
И	Л	Л	Л	И	И	И
Л	И	И	И	Л	И	И
Л	И	Л	И	Л	И	И
Л	Л	И	И	И	И	И
Л	Л	Л	И	И	И	И

Из составленных таблиц видно, что данные формулы не равносильны.

Основные равносильности.

Для любых формул А, В и С справедливы следующие равносильности:

A & B º B & A; A & A º A; A & (B & C) º (A & B) & C;

A Ú B º B Ú A; A Ú A º A; A Ú (B Ú C) º (A Ú B) Ú C;

A Ú (B & C) º (A Ú B) & (A Ú C); A & (B Ú C) º (A & B) Ú (A & C);

A & (A Ú B) º A; A Ú (A & B) º A; ØØA º A; Ø(A & B) º ØA Ú ØB;

A º (A & B) Ú (A & ØB); A º (A Ú B) & (A Ú ØB);

Булевы функции.

Определение. Булевой функцией f(X1, X2, …, Xn) называется называется произвольная n – местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

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

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

X1	X2	ØX1	X1&X2	X1ÚX2	X1ÞX2	X1ÛX2
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

Исчисление предикатов.