Основные законы алгебры логики

В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений (см. Таблицу5.)

Таблица 5. Основные законы алгебры логики

Закон	Для ИЛИ	Для И
Переместительный	xÚy = yÚx	xÙy = yÙx	(3)
Сочетательный	xÚ(yÚz) = (xÚy)Úz	xÙ(yÙz) = (xÙy)Ùz	(4)
Распределительный	xÙ(yÚz) = xÙyÚ xÙz	xÚ yÙz = (xÚy) Ù (xÚz)	(5)
Правила Де Моргана	( xÚy)= xÙ(y)	(xÙy)= xÚ(y)	(6)
Идемпотенции	xÚx=x	xÙx=x	(7)
Поглощения	xÚxÙy=x	xÙ(xÚy)=x	(8)
Склеивания	xÙyÚ(x)Ùy=y	(xÚy)Ù (xÚy)=y	(9)
Операция с переменной с ее инверсией	xÚ(x)=1	xÙ(x)=0	(10)
Операция с константами	xÚ1=x; xÚ0=х	xÙ1=x; xÙ0=0	(11)
Операция двойного отрицания	(x)=x	(12)

Примеры задач с таблицами истинности:

Изучите примеры задач с таблицами истинности из презентации:

Задание 1. (Задание А11 демоверсии 2004 г.)

Для какого имени истинно высказывание:

(Первая буква имени гласная → Четвертая буква имени согласная)

1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР

Решение.

Введем обозначения для высказываний:

А = «Первая буква имени гласная» (13)

В = «Четвертая буква имени согласная» (14)

тогда наше высказывание примет вид: (A → B). Чтобы преобразовать высказывание, воспользуемся тождествами (1), (6), (12):

₍₁₎ ₍₆₎ ₍₁₂₎

(A → B) = ((A) Ú B) = (A) Ù (B) = A Ù (B)

Используя обозначения (13), (14), получим, что исходное высказывание равносильно следующему:

Первая буква гласная Ù (Четвертая буква имени согласная), «

Первая буква гласная Ù Четвертая буква имени гласная.

Этому условию удовлетворяет только имя АНТОН (вариант ответа №3).

Ответ: 3

Задание 2. (Задание А12 демоверсии 2004 г.)

Какое логическое выражение равносильно выражению (A Ú B)

1) AÚB 2) AÙB 3) AÚB 4) AÙB

Решение.

Чтобы преобразовать высказывание, воспользуемся законами (6), (12):

_{(6) (12)}

(A Ú B) = A Ù (B) = A Ù B, что соответствует ответу №4.

Ответ: 4

Задание 3. (Задание А13 демоверсии 2004г., А11 демоверсий 2005, 2006г.)

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

X Y Z F

Какое выражение соответствует F?

1) XÙYÙZ 2) XÚYÚZ 3) XÚYÚZ 4) XÚYÚZ

Решение.

Способ 1. Наличие двух единиц в столбце F позволяет предположить использование дизъюнкции в логическом выражении. F принимает значение, равное 0, при X=0, Y=0, Z=1, что соответствует логической сумме XÚYÚZ. При проверке этой формулы при значениях первой и третьей строки, получаем верные значения F.

Способ 2. Проверим предложенные ответы:

1) F=XÙYÙZ=0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы.

2) F=XÚYÚZ=1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

3) Выражение XÚYÚZ соответствует F при всех предложенных комбинациях X,Y,Z.

4) F=XÚYÚZ=1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Таким образом, верный вариант ответа №3.

Ответ: 3

Задание 4. (Задание А9 демоверсий 2005 г., 2006 г.)

Для какого числа X истинно высказывание

X>1 Ù ((X<5)→(X<3)) (15)

1) 1 2) 2 3) 3 4) 4