Построение таблиц истинности и упрощение(минимизация) логических выражений различными методами

Математическая логика. высказываниями.В математической логике все суждения называются высказываниями. Все высказывания обозначаются через латинские переменные:A,B,C…Их называют логическими переменными Все простые высказывания обозначаются через латинские переменные:A,B,C…Их называют логическими переменными В математической логике все истинные высказывания обозначаются через 1,а ложные через 0. В математической логике все истинные высказывания обозначаются через 1,а ложные через 0.

Логические функции. Сложное высказывание называется логической функцией. В математической логике связка «и» называется конъюнкция, «или»- дизъюнкция, «не»-инверсия.

Конъюнкция. Конъюнкция обозначается знаком «^» и называется логическим умножением. Конъюнкция от двух логических переменных истинна тогда и только тогда,когда истинны обе эти переменные.

Дизъюнкция. Дизъюнкция обозначается знаком «\/» и называется логическим сложением. Дизъюнкция от двух логических переменных ложна тогда,когда ложны две переменные,входящие в нее.

Инверсия. Инверсия-это логическое отрицание,обозначается знаком «¬»-не. Отрицание ложного высказывания-это всегда истинное,отрицание истинного высказывания-ложное.

Таблица истинности для конъюнкции. ABF

Таблица истинности для дизъюнкции. ABF

Таблица истинности для инверсии. AF 01 10

Построение таблиц истинности. 1 столбец таблицы делится пополам:верхняя часть заполняется 0,а нижняя 1. 2 столбец продолжается делиться пополам и записывается в группы,состоящие из нулей и единиц. Для последнего столбца должна получиться запись из нулей и единиц.

Приоритет операций. Приоритет операций таков: 1. инверсия 2. конъюнкция 3.дизъюнкция

Равносильные логические выражения. Логические выражения,у которых последние столбцы таблиц истинности совпадают,называются равносильными.Логические выражения,у которых последние столбцы таблиц истинности совпадают,называются равносильными. Для обозначения равносильных логических выражений используется знак «=».Для обозначения равносильных логических выражений используется знак «=».

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

Логическое следование(импликация). Логическая операция импликации «если A, то B»,обозначается A B. Составное высказывание,образованное с помощью операции логического следования (импликации),ложно тогда и только тогда,когда из истинной предпосылки(первого высказывания) следует ложный вывод(второе высказывание).

Таблица истинности логической функции «импликация» ABF

Логическое равенство (эквивалентность). Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «…тогда и только тогда,когда…».

Логическое равенство (эквивалентность). Логическая операция эквивалентности «A тогда и только тогда,когда B» обозначается A~B. Составное высказывание,образованное с помощью логической операции эквивалентности истинно тогда только тогда,когда оба высказывания одновременно либо ложны,либо истинны.

Таблица истинности логической функции эквивалентности. ABF

Логические законы и правила преобразования логических выражений. Законы логики отражают наиболее важные закономерности логического мышления.В алгебре высказываний законы логики записываются в виде формул,которые позволяют проводить эквивалентные преобразования логических выражений.

Свойства,позволяющие упрощать логические выражения. конъюнкция дизъюнкция инверсия A^A=0AvA=1A=A A^A=AAvA=A A^0=0Av0=A A^1=AAv1=1

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

Законы логики. Переместительный закон: AvB=BvA; А^В=В^A Сочетательный закон: (AvB)vC=Av(BvC);(A^B)^C=A^(B^C) Распределительный закон: (АvB)^C=A^CvB^C Законы инверсии или формулы де Моргана: AvB=A ^B; A^B=AvB

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

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

Построение СДНФ. Каждой строчке,в которой значение функции равно 1,соответствует элементарная конъюнкция.Чтобы выписать ее,надо записать аргумент функции,если его значение в этой строчке равно 1 и отрицание аргумента,если его значение равно 0.

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

Построение СКНФ. Чтобы построить СКНФ по таблице истинности,надо выбрать строчки,в которых значение функции равно 0. При построении элементарной дизъюнкции надо выписывать сам аргумент,если его значение равно 0 и его отрицание,если его значение равно 1. При упрощении того или иного выражения мы выясним,что они равнозначны.

Соседние конъюнкции. Конъюнкции,которые отличаются представлением одной переменной,называются соседними. AB и AB-не соседние конъюнкции.

Склеивание. Две соседние конъюнкции склеиваются с образованием одной конъюнкции меньшего ранга.Исчезает та переменная,по которой конъюнкции склеиваются.

Метод Квайна-Мак Класски. Данный метод основывается на задании входящих в СДНФ элементарных конъюнкций в виде двоичных чисел,называемых номерами соответствующих наборов.Кроме номера каждому произведению присваивается определенный индекс,под которым понимается число единиц в двоичном представлении данного набора.Далее производится склеивание различных наборов.