Элементарные функции алгебры логики
Свой-ва: могут формировать базис, то есть ими можно описать любые другие функции.
1. Конъюнкция (логическое умножение) “И” (&;*;^)
2. Дизъюнкция (логическое сложение) “ИЛИ” (+; v)
3. Отрицание (инверсия) “НЕ” ()
4. “Штрих Шеффера” () “И-НЕ” (|)
5. “Стрелка Пирса” () “ИЛИ-НЕ” (↓)
Аргументы | Конъюнкция | Дизъюнкция | Отрицание | “Штрих Шеффера” | “Стрелка Пирса” | |
0 | 0 | 0 | 0 | 1 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 0 | 1 | 0 |
1 | 0 | 0 | 1 | 0 1 | 1 | 0 |
1 | 1 | 1 | 1 | 0 0 | 0 | 0 |
Базисом называется совокупность элементарных функций, обладающее свойством, что через них можно выразить функцию алгебры логики.
Известно 3 базиса:
· “И”, “ИЛИ”, “НЕ”
· “И-НЕ”
· “ИЛИ-НЕ”
Основные эквивалентности. Способы представления ФАЛ: таблица истинности, совершенные нормальные формы, сокращенные способы записи.
Свойство Эквивалентности
Функция эквивалентна другой функции, если она принимает те же значения на тех же самых наборах (если таблицы истинности совпадают)
Законы:
1) Переместительный (коммутативности)
|
|
А+В=В+А
А*В=В*А
2) Сочетательный (ассоциативности)
(А+В)+С=А+(В+С)
(А*В)*С=А*(В*С)
3) Двойственности (инверсии) де Моргана
4) Распределительный (дистрибутивности)
(А+В)*С=АС+ВС
(А*В)+С=(А+С)*(В+С)
Тождества:
А+0=А, А*0=0, А+1=1, А*1=А
А+А=А, А*А=А, А+ =1, А* =0, =А.
Таблица Истинности функции - канонический способ задания функции алгебры логики, где область аргументов функции представлена в виде упорядоченной последовательности их двоичных эквивалентов, а область значений функции представлена путём сопоставления в той же стороне значения функции на каждом наборе переменных.
Совершенная Дизъюнктивная Нормальная Форма – представление дизъюнкции элементарных конъюнкций, в каждый из который входят все переменные.
Совершенная Конъюнктивная Нормальная Форма – представление конъюнкции элементарных дизъюнкций, в каждый из который входят все переменные.
Термы, составляющие функцию, записываются как их двоичные эквиваленты (а=1; =0)
Сокращённые формы записи СДНФ/СКНФ:
F(a,b,c,d)= /