11. Алгебра логики. Переменные и константы алгебры логики.
Алгебра логики — раздел математической логики, в котором изучаются логические операции над высказываниями. Предполагается двоичная логика, высказывания только истинны или ложны.
Логические функции. Независимые высказывания называют аргументами. Высказывания, истинность либо ложность которых зависит от истинности либо ложности других высказываний, называют логическими функциями, зависящими от своих аргументов: y=f(x), y=f(x1,x2,x3) итп.
Для упрощения записей значения Ложь(0) и Истина(1) обозначают нулем и единицей.
Логические переменные могут принимать только эти два зн-я.
Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.
Аксиомы алгебры логики: x*0=0, x+0=x, x*1=x, x+1=1, x*x=x, x+x=x, x+x_=1, x*x_=0.
Склеивание(одинаковые остаются) a*x+a*x_=a*(x+x_)=a*1=a.
a*x и a*x_ называются соседними и склеиваются по икс.
12. Законы и аксиомы алгебры логики. Логические функции.
Законы и аксиомы алгебры логики(АЛ). АЛ рассматривает выссказывания и их взаимосвязь только с точки зрения их истинности либо ложности. Если x – это высказывание, то в алгебре логики x=True(x=Истина) либо x=False(x=Ложь).
Аксиомы алгебры логики: x*0=0, x+0=x, x*1=x, x+1=1, x*x=x, x+x=x, x+x_=1, x*x_=0.
Склеивание(одинаковые остаются) a*x+a*x_=a*(x+x_)=a*1=a.
a*x и a*x_ называются соседними и склеиваются по икс.
Законы булевой алгебры
ассоциативный
x1*(x2*x3)=(x1*x2)*x3
x1+(x2+x3)=(x1+x2)+x3
коммутативный
x1*x2=x2*x1
x1+x2=x2+x1
дистрибутивный
x1*(x2+x3)=x1*x2+x1*x3
x1+(x2*x3)=(x1+x2)*(x1+x3)
Правило де Моргана x1*x2=x1+ x2, x1+x2=x1*x2 или x1∧x2=x1∨x2, x1∨x2=x1∧x2
Логические функции. Независимые высказывания называют аргументами. Высказывания, истинность либо ложность которых зависит от истинности либо ложности других высказываний, называют логическими функциями, зависящими от своих аргументов: y=f(x), y=f(x1,x2,x3) итп. Для упрощения записи значений Ложь и Истина обозначают 0 и 1.
Формы представления логических функций: —Таблица истинности —Аналитическое выражение —Логическая схема
Таблица истинности описывает значения логических функций на всех наборах её аргументов. Для ф-ции, зависящей от n аргументов, рассматривается N=2^n значений.
x1x2x3y
0000
0010
0101
0111
1000
1011
1101
1110
13. Конъюнкция. Дизъюнкция. Инверсия. Функционально полная система лф. Функции и-не, или-не, Исключающее или.
Конъюнкция(И)(∧)(аналог умножения)истина тогда и только тогда, когда истинны все её аргументы.
Правило: результат равен наименьшему значению.
x1x2y
000 y=x1∧x2
010 y=x1&x2
100 y=x1*x2
111 y=x1x2
Дизъюнкция(ИЛИ)(∨)(сложение)истинна, если истинен хотя бы один из её аргументов.
Правило: результат 0, если все операнды 0, во всех ост 1.(max(a,b))
x1x2y
000 y=x1∨x2
011
101 y=x1+x2
111
Инверсия(НЕ) принимает значение, противоположное значению ее аргумента.
xy
01 y=|x|
10
14. Формы представления ЛФ. Таблица истинности. СДНФ и СКНФ. Переход от одной формы к другой.
Таблица истинности описывает значения логических функций на всех наборах её аргументов. Для ф-ции, зависящей от n аргументов, рассматривается N=2^n значений.
x1x2x3y
0000
0010
0101
0111
1000
1011
1101
1110
СДНФ и СКНФ
СДНФ — совершенная дизъюнкция нормальная форма представления логической функции. СДНФ — это дизъюнкция конъюнкции.
СКНФ — совершенная конъюнктивная нормальная форма представления логической функции. СКНФ — это конъюнкция дизъюнкции.
СДНФ из таблицы истинности. Чтобы записать СДНФ функции, нужно записать все конституенты единицы(т.е. конъюнкции), причем переменная, принимающая на соответствующем наборе значение «0», записывается с инверсией. Все коньюнкции соединить знаком дизъюнкции.
15. Преобразование логических выражений. Склеивание. Минимизация логических выражений.
Минимизация логических выражений:
Аксиомы алгебры логики: x*0=0, x+0=x, x*1=x, x+1=1, x*x=x, x+x=x, x+x_=1, x*x_=0.
Склеивание(одинаковые остаются) a*x+a*x_=a*(x+x_)=a*1=a.
a*x и a*x_ называются соседними и склеиваются по икс.