Дискретная математика (стр. 3 из 10)
5. Законы истины и лжи (свойства констант):
6. Законы идемпотентности:
7. Коммутативные законы:
8. Ассоциативные законы:
– дизъюнкции 
– конъюнкции9. Дистрибутивные законы:
– 1‑ый дистрибутивный закон 
– 2‑ой дистрибутивный закон10. Законы поглощения:
11. Законы де Моргана:
12. Закон импликации:
13. Закон эквивалентности:
14. Свойства сложения «по модулю два»:
Справедливость этих законов можно доказать с помощью таблиц истинности сложных логических связей описываемых законов.
Следствия из законов алгебры логики (часто используются при упрощении логических выражений).
1. Правило поглощения. Данное правило является следствием из дистрибутивного закона. Оно может быть записано в следующем виде:
.2. Правило свертки. Правило является следствием из второго дистрибутивного закона. Запись правила:
а)
;б)
.3. Правило расширения. Правило записывается в следующем виде:
.4. Правило склеивания. Базируется на понятии соседних конъюнкций. Соседними называются конъюнкции, отличающиеся представлением одной переменной. Например, конъюнкции
и 
, 
и 
являются попарно соседними. В первой паре конъюнкции отличаются представлением х2, а во второй – представлением х1. По этим переменным конъюнкции склеиваются.Формулировка правила: две соседние конъюнкции склеиваются с образованием одной конъюнкции меньшего ранга; исчезает та переменная, по которой конъюнкция склеивается.
, 
.Контрольные вопросы
1. Перечислите основные законы алгебры логики. Как дозывается их справедливость?
2. Перечислите следствия из законов алгебры логики.
3.5 Логические функции многих переменных
Все логические операции, которые были рассмотрены в 3.2, распространяются и на функции нескольких переменных. Теперь будем рассматривать функции F(x1, x2,…, xn), где xi – логические переменные, которые принимают значения нуля или единицы. Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики, или булева алгебра. Два элемента алгебры логики – ее константы – 0 (ложь) и 1 (истина). Во всех компьютерах используются сигналы двух видов. Сигналы можно интерпретировать как двоичные числа, или логические переменные.
Логической функциейF от набора логических переменных х1,…, хn называется функция, которая может принимать только два значения: логический 0 и логическая 1.
Область определения логической функции конечна и зависит от количества возможных наборов аргументов. Если n – число аргументов, то количество возможных наборов аргументов равно 2n.
Множество значений функции F(x1,…, xn) – это множество {0,1}, т. е. F=0 либо 1.
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются наборы аргументов, а в правой – соответствующие значения функции.
| x1 | x2 | … | xn-1 | xn | F(x1, x2,…, xn-1, xn) |
| 0 | 0 | … | 0 | 0 | F (0,0,…, 0,0) |
| 0 | 0 | … | 0 | 1 | F (0,0,…, 0,1) |
| 0 | 0 | … | 1 | 0 | F (0,0,…, 1,0) |
| … | … | … | … | … | … |
| 1 | 1 | … | 1 | 1 | F (1,1,…, 1,1) |
Вектором значений булевой функции F(x1,…, xn) называется упорядоченный набор всех значений функции F, при которых значения упорядочены по лексикографическому порядку множества аргументов {0,1}n.
Поскольку всего имеется 2n наборов
нулей и единиц (|{0,1}n|=2n), существует ровно 
булевых функций F(x1,…, xn) от n переменных: 
.При n=2 количество функций равно 16, при n=3 – 256 и т. д. На рис. 3 представлены в упорядоченном виде наборы аргументов для ряда функций – отрицания 0, функций одного, двух и трёх аргументов.
Рис. 3. Упорядоченные наборы аргументов
3.6 Построение формул алгебры логики по заданной таблице истинности
Пусть F – двоичная функция от nпеременных. Предположим, что F не равна тождественно нулю. Пусть T1, T2,…, Tk – все точки ее определения, в которых F=1. Можно доказать, что справедлива следующая формула:
,где
, j=1,2,…, k, 
Построить функцию F можно и по-другому. Если функция Fне равна тождественно единице и S1, S2,…, Sm – все точки области ее определения, в которых F=0, то справедлива формула:
,где
, j=1,2,…, m. 
Из приведенных формул видно, что любую двоичную функцию можно записать, используя лишь операции ¬,
, 
.Основная конъюнкция – это конъюнкция основных высказываний переменных или их отрицаний. Например,
.Основная дизъюнкция – это дизъюнкция основных высказываний переменных или их отрицаний. Например,
.Конъюнктивной нормальной формой (КНФ) данной формулы называется формула, равносильная данной и представленная в виде конъюнкции основных дизъюнкций. Например, (A+B) (A+C+B) (D+A).
Дизъюнктивной нормальной формой (ДНФ) данной формулы называется формула, равносильная данной и представленная в виде дизъюнкции основных конъюнкций. Например, AB+C+AC.
Теорема 1. Для того чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы ее КНФ содержала в каждой элементарной дизъюнкции некоторое высказывание и его отрицание.