 |
Простейшие логические функции
|
|
|
|
1) Логическое умножение или конъюнкция:
Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B.
Таблица истинности для конъюнкции
A B F
1 1 1
1 0 0
0 1 0
0 0 0
2) Логическое сложение или дизъюнкция:
Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B.
Таблица истинности для дизъюнкции
A B F
1 1 1
1 0 1
0 1 1
0 0 0
3) Логическое отрицание или инверсия:
Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Таблица истинности для инверсии
A неА
1 0
0 1
4) Логическое следование или импликация:
Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. Тоесть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.
Таблица истинности для импликации
A B F
1 1 1
1 0 0
0 1 1
0 0 1
5) Логическая равнозначность или эквивалентность:
Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
|
|
|
Таблица истинности для эквивалентности
A B F
1 1 1
1 0 0
0 1 0
0 0 1
Порядок выполнения логических операций в сложном логическом выражении
1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Таблица истинности для функции двух переменных
F1 – const 0 – постоянная 0
F2 – логическое умножение – конъюнкция (А И В).
F3 – отрицание логического следствия - НЕ (ЕСЛИ А ТО В).
F4 – аргумент А.
F5 – отрицание обратного логического следствия - НЕ (ЕСЛИ В ТО А).
F6 – аргумент В.
F7 – отрицание логической равнозначности - НЕ (А тогда и только тогда, когда В).
F8 – логическое сложение - дизъюнкция (А ИЛИ В).
F9 – отрицание логического умножения – НЕ (А И В).
F10 – логическая равнозначность - эквиваленция (А тогда и только тогда, когда В).
F11 – логическое отрицание аргумента B – инверсия (НЕ В).
F12 – обратное логическое следствие - импликация (ЕСЛИ В ТО А)
F13 – логическое отрицание аргумента А – инверсия (НЕ А).
F14 – логическое следствие - импликация (ЕСЛИ А ТО В).
F15 – отрицание логического сложения - НЕ (А ИЛИ В).
F16 – const 1 – постоянная 1
КНФ и ДНФ
Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.
Алгоритм построения ДНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
|
|
|
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ.[1] Для этого можно использовать: Закон двойного отрицания, Закон де Моргана, Дистрибутивность.
Алгоритм построение см. ДНФ
СКНФ и СДНФ
СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных конъюнкций
в каждой конъюнкции нет одинаковых пропозициональных букв
каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.
Для любой функции алгебры логики существует своя СДНФ, причем единственная.
СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных дизъюнкций
в каждой дизъюнкции нет одинаковых пропозициональных букв
каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.
Правила преобразования
А + В = В + А АВ = ВА
(А + В) + С = (А + С) + В (АВ)С = (АС)В
А(В + С) = АВ + АС А + (ВС) = (А + В)(А +С)
 |
А + В = `А ×`В А × В = `А +`В
А + А = А А А = А
 |
А = А А +`АВ = А + В
А + АВ = А А×(А + В) = А
А +`А = 1 А ×`А = 0
А + 0 = А А × 0 = 0
А + 1 = 1 А × 1 = А
Таблица истинности
Таблица истинности — это таблица, описывающая логическую функцию.
Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь» (либо 1, либо 0).
Табличное задание функций встречается не только в логике, но для логических функций таблицы оказались особенно удобными, и с начала XX века за ними закрепилось это специальное название. Особенно часто таблицы истинности применяются в булевой алгебре и в аналогичных системах многозначной логики.
|
|
|
Карта Карно
Комбинационная логика
В теории цифровых устройств комбинационной логикой называют логику функционирования устройств комбинационного типа. У комбинационных устройств состояние выхода однозначно определяется набором входных сигналов. Это отличает комбинационную логику от секвенциальной логики, в рамках которой выходное значение зависит не только от текущего входного воздействия, но и от предыстории функционирования цифрового устройства. Другими словами, секвенциальная логика предполагает наличие памяти, которая в комбинационной логике не предусмотрена.
Характеристика
Комбинационная логика используется в вычислительных цепях для формирования входных сигналов и для подготовки данных, которые подлежат сохранению. На практике вычислительные устройства обычно сочетают комбинационную и секвенциальную логику. Например, компьютерное Арифметическое Логическое Устройство для математических вычислений содержит комбинационные узлы. Математику комбинационной логики обеспечивает Булева алгебра. Базовыми операциями являются: конъюнкция х ^ у, дизъюнкция хVу и отрицание х_. В комбинационных схемах используются логические элементы: конъюнктор, дизъюнктор, инвертор, а также производные элементы: И-НЕ, ИЛИ-НЕ и «Равнозначность». Наиболее известные комбинационные устройства — это сумматор, полусумматор, шифратор, дешифратор, мультиплексор и демультиплексор.
Временные гонки»
|
|
|
