Материал: Лекция 7

Лекция 7. Логические функции двух переменных. Композиции логических функций. Эквивалентные логические функции

Некоторые из логических функций двух переменных (см. таблицу 2 лекции 2) имеют специальные названия и обозначения:

a) f2;0(x1; x2) 0 константа ноль. Таблица 1

b) f2;1(x1; x2) = x1 ^x2 конъюнкция x1 и x2 (читается “x1 и x2”). Отметим, что x1 ^ x2 = minfx1; x2g. Конъюнкцию часто называют логическим умножением и обозначают также x1 x2 или x1x2.

Замечание 1 (расширенная интерпретация конъюнкции). Если 0 – ложь и 1 – истина, то конъюнкцию можно интерпретировать так:

а) ложь и ложь – ложь, б) ложь и истина – ложь, в) истина и ложь – ложь,

г) истина и истина – истина. Таблица 2

Замечание 2. Здесь и далее второй индекс функции (ее номер среди функций двух переменных) соответствует двоичному числу, образованному значениями этой функции на наборах значений аргументов, расположенных в лексикографическом порядке. Так,

6 = 0 23 + 1 22 + 1 21 + 0 20.

Таблица 3

1

d) f2;7(x1; x2) = x1 _x2 дизъюнкция x1 и x2 (читается: x1 или x2). Отметим, что x1 _ x2 = maxfx1; x2g. Дизъюнкцию часто называют логическим сложением и обозначают также x1 + x2.

Замечание 3 (расширенная интерпретация дизъюнкции). Если 0 – ложь и 1 – истина, то дизъюнкцию можно интерпретировать так:

а) ложь или ложь – ложь, б) ложь или истина – истина, в) истина или ложь – истина,

г) истина или истина – истина.

Таблица 4

e) i = 9 : f2;9(x1; x2) = x1 x2 эквиваленция (равная 1, если x1 и x2 равны между собой, и 0 в противном случае).

Таблица 7

Замечание 4 (расширенная интерпретация эквиваленции). Если 0 – ложь и 1 – истина, то эквиваленцию можно интерпретировать так:

а) ложь равносильна лжи – истина, б) ложь равносильна истине – ложь, в) истина равносильна лжи – ложь,

г) истина равносильна истине – истина.

f) i = 13 : f2;13(x1; x2) = x1 ! x2 импликация x1 и x2 (читается: из x1 следует x2). Эту функцию часто называют логическим следованием.

Таблица 8

Замечание 5 (расширенная интерпретация импликации). Если 0 – ложь и 1 – истина, то импликацию можно интерпретировать так:

2

а) из лжи может следовать ложь – истина, б) из лжи может следовать истина – истина, в) из истины может следовать ложь – ложь,

г) из истины может следовать истина – истина. g) f2;15(x1; x2) = 1 константа единица.

Таблица 5

В общем случае число различных логических функций n переменных обозначается P2(n) (индекс 2, как и выше, означает количество возможных значений каждого аргумента).

Упражнение 1 (д/з). Доказать методом математической индукции, что P2(n) = 22n – число различных двоичных векторов длины 2n.

Определение 1. Функция, полученная путем применения логической функции f0(x1; : : : ; xn) к значениям логических функций f1(x1; : : : ; xm); : : : ; fn(x1; : : : ; xm), называется композицией логических функций:

f(x1; : : : ; xm) = f0(f1(x1; : : : ; xm); : : : ; fn(x1; : : : ; xm)):

Иcпользуя композиции логических функций, можно получать другие логические функции.

Пример 1. Из f2;7(x1; x2) с помощью функции отрицания f1;2(x) получить f1;2(f2;7(x1; x2)) f2;7(x1; x2).

Решение:

Таблица 1

Пример 2. Из f2;2(x1; x2) и f2;3(x1; x2) с помощью функции конъюнкции f2;1(x1; x2)

получить f2;1(f2;2(x1; x2); f2;3(x1; x2)) f2;2(x1; x2) ^ f2;3(x1; x2).

3

Решение:

Таблица 3

Упражнение 1 (д/з). Из f2;1(x1; x2) и f2;3(x1; x2) с помощью функции дизъюнкции f2;7(x1; x2) получить f2;7(f2;1(x1; x2); f2;3(x1; x2)) f2;1(x1; x2) _ f2;3(x1; x2).

Определение 2. Эквивалентными логическими функциями называются функции, имеющие одинаковые таблицы задания. Будем обозначать эквивалентные функции так: f1(x1; : : : ; xn) f2(x1; : : : ; xn).

Пример 3. f2;11(x1; x2) f2;4(x1; x2), как видно из следующей таблицы: Таблица 5

Упражнение 2 (д/з). Доказать: f2;2(x1; x2) f2;13(x1; x2), f2;4(x1; x2) f2;5(x1; x2)^ f2;6(x1; x2).

4