Функция F₁(х) = х, т. е. функция F₁повторяет х;

Функция F₂(х) является отрицанием х (логическая операция НЕ) и обозначается

Все перечисленные функции являются унарными (для одной переменной) функциями.

2) Две переменные имеют 16 логических функций (таблица 2).

Таб. 2

х₁	х₂	F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Все функции в таблице 2 являются бинарными (для двух переменных).

Функции F₀и F₁₅ – константы 0 и 1;

Функция F₁(х_1,х₂) называется конъюнкцией х₁и х_2,обозначается: &,

,но чаще всего значок конъюнкции опускают, аналогично знаку умножения. Она ровна единице только тогда когда х₁и х₂=1. В остальных случаях она ровна 0. Это функция логического «И» или функция логического умножения.

Функция F₇(х_1,х₂) называется дизъюнкцией х₁и х_2,обозначается +,

. Она ровна 1, если хотя бы одна переменная равна 1. Это функция логического «ИЛИ» или функция логического сложения.

Функция F₆(х_1,х₂) – сложение по модулю 2, обозначается

. Она ровна 1 когда значения ее аргументов различны и ровна 0 когда значения ее аргументов ровны, поэтому эта функция называется неравнозначностью.

Функция F₉(х_1,х₂) – эквивалентность (равнозначность), обозначается «

». Она ровна 1 когда аргументы ровны и ровна 0 когда аргументы различны.

Функция F₁₃(х_1,х₂) – импликация, обозначается

. Звучит данная функция так: “если х_1,то х₂ “ .

Функция F₈(х_1,х₂) – стрелка Пирса, обозначается

Функция F₁₄(х_1,х₂) – штрих Шеффера, обозначается х_1,х₂

Остальные функции своего названия не имеют, и легко выражаются через перечисленные выше функции.

При построении таблицы для конкретной формулы необходимо «разложить формулу по ее составляющим», т. е. по числу операций следуя изнутри наружу. для каждой операции составляется таблица истинности, а в последнем столбце записывается вся формула (или ставится буква f) и составляется таблица для нее.

Задание №4

Построить таблицу истинности для формулы:

Таб. 3

X	Y				f
0	0	1	0	1	1
0	1	1	0	1	1
1	0	0	0	0	1
1	1	1	1	0	1

3. БУЛЕВА АЛГЕБРА

Множество В, на котором определены две бинарные операции (конъюнкция

и дизъюнкция

) и одна унарная операция (отрицание

) и выделены два элемента 0 и 1

называется булевой алгеброй.

Причем для этих операций необходимо выполнение следующих свойств:

1. Ассоциативность

2. Коммутативность

3. Дистрибутивность конъюнкции относительно дизъюнкции

4. Дистрибутивность дизъюнкции относительно конъюнкции

5. Идемпотентность

6. Двойное отрицание

7. Свойства констант

8. Правила де Моргана

9. Закон противоречия

10. Закон исключенного третьего

В алгебре логики эти законы называются равносильностями.

3.1 Совершенные нормальные формы

3.1.1 Совершенная дизъюнктивная нормальная форма

Введем обозначения:

; А^А=1; Х^А=1, если Х=А, Х^А=0, если Х

А.

Формула Х^А_1……Х^А_n, где А=

- какой-либо двоичный набор, а среди переменных Хi могут быть совпадающие называется элементарной конъюнкцией.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

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

Например: 1)

(значок конъюнкции в данном случае опущен).

1),4) – правильные элементарные конъюнкции;

2)– переменная х входит один раз сама и второй раз под знаком отрицания;

3) – переменная y входит трижды: один раз сама и два раза под знаком отрицания.

Правильная элементарная конъюнкция называется полной относительно переменных х₁…..х_n, если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Например: из перечисленных в предыдущем примере конъюнкций полной является только 4) относительно переменных x,y,z,t; а относительно переменных x,y,z полной является только 1).

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных х₁…..х_nназывается дизъюнктивная нормальная форма_,в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных х₁…..х_n

3.1.2 Разложение по переменным

Теорема 1. Всякая логическая функция может быть представлена в СДНФ:

, (1)

где m

, а дизъюнкция берется по всем 2^m наборам значений переменных х₁,…х_m . Функция f разложена по первым n-переменным. Данное равенство называется разложением по переменным. х₁,…х_m. Например при n=4, m=2 разложение имеет вид:

теорема доказывается подстановкой в обе части равенства (1) произвольного набора (b₁,…,b_m, b_m₊₁,…,b_n) всех n-переменных.

При m = 1 из (1) получаем разложение функции по одной переменной:

(2)

Очевидно, что аналогичное разложение справедливо для любой из n- переменных.

Основные положения дискретной математики (стр. 5 из 11)

3. БУЛЕВА АЛГЕБРА

3.1 Совершенные нормальные формы

(2)