Элементарные логические функции, Понятие Базиса

Конъюнкция

Дизъюнкция

“Штрих Шеффера”

“Стрелка Пирса”

1 2 3 4 5 6 7

Элементарные функции алгебры логики
Свой-ва: могут формировать базис, то есть ими можно описать любые другие функции.

1. Конъюнкция (логическое умножение) “И” (&;*;^)

2. Дизъюнкция (логическое сложение) “ИЛИ” (+; v)

3. Отрицание (инверсия) “НЕ” ()

4. “Штрих Шеффера” () “И-НЕ” (|)

5. “Стрелка Пирса” () “ИЛИ-НЕ” (↓)

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

· “И”, “ИЛИ”, “НЕ”

· “И-НЕ”

· “ИЛИ-НЕ”

Основные эквивалентности. Способы представления ФАЛ: таблица истинности, совершенные нормальные формы, сокращенные способы записи.

Свойство Эквивалентности

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

Законы:

1) Переместительный (коммутативности)

А+В=В+А

А*В=В*А

2) Сочетательный (ассоциативности)

(А+В)+С=А+(В+С)

(А*В)*С=А*(В*С)

3) Двойственности (инверсии) де Моргана

4) Распределительный (дистрибутивности)

(А+В)*С=АС+ВС

(А*В)+С=(А+С)*(В+С)

Тождества:

А+0=А, А*0=0, А+1=1, А*1=А

А+А=А, А*А=А, А+ =1, А* =0, =А.

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

Совершенная Дизъюнктивная Нормальная Форма – представление дизъюнкции элементарных конъюнкций, в каждый из который входят все переменные.

Совершенная Конъюнктивная Нормальная Форма – представление конъюнкции элементарных дизъюнкций, в каждый из который входят все переменные.

Термы, составляющие функцию, записываются как их двоичные эквиваленты (а=1; =0)