Упрощение формул логики с помощью равносильных преобразований: Упрощение формул логики с помощью равносильных преобразований

Содержание

Упрощение формул логики с помощью равносильных преобразований

Это символы не жёстко привязаны к соотв. операциям, можно использовать другие.

Примеры логических выражений

С применением отрицания

Со знаком «эквивалентно»

Со знаком «следствие»

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

Равносильные формулы алгебры логики

Определение. Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулы элементарных высказываний (переменных).

Обозначение. A ≡ B .

Определение. Формула A называется тождественно истинной (тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных (напр., ).

Определение. Формула A называется тождественно ложной (противоречием), если она принимает значение 0 при всех значениях входящих в нее переменных (напр.,

Утверждение. Отношение равносильности рефлексивно, симметрично, транзитивно.

Связь между понятиями равносильности и эквивалентности: если формулы A и B равносильны, то формула A ↔ B тавтология, и обратно, если формула A ↔ B тавтология, то формулы A и B равносильны.

Равносильности алгебры логики можно разбить на 3 группы:

1. Основные равносильности.

· – законы идемпотентности;

· ;

· – закон противоречия;

· – закон исключенного третьего;

· – закон снятия двойного отрицания;

· – законы поглощения.

1. Равносильности, выражающие одни логические операции через другие:

· ;

;

· ;

· .

Замечание. Из равносильностей группы 2 следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание, или дизъюнкцию и отрицание. Дальнейшее исключение операций невозможно. Например, если использовать только конъюнкцию, то уже такая простая формула, как не может быть выражена с помощью операции конъюнкции.

Существуют операции, с помощью которых может быть выражена любая из 5 логических операций:

1) Связка Шеффера – дизъюнкция отрицаний.

Обозначение. x | y ≡ (« x не совместно с y »).

Логические значения связки Шеффера описываются следующей таблицей истинности:

Имеют место следующие равносильности: а) ; б) .

2) Связка Лукасевича – конъюнкция отрицаний.

Обозначение . x ↓ y ≡ («ни x , ни y »).

Логические значения связки Лукасевича описываются следующей таблицей истинности:

2. Равносильности, выражающие основные законы алгебры логики:

· – коммутативность конъюнкции;

· – коммутативность дизъюнкции;

· – ассоциативность конъюнкции;

· – ассоциативность дизъюнкции;

· – дистрибутивность конъюнкции относительно дизъюнкции;

· – дистрибутивность дизъюнкции относительно конъюнкции.

Замечание. Равносильности группы 3 показывают, что над формулами алгебры логики можно проводить те же преобразования, что и в алгебре чисел.

Равносильные преобразования формул

Используя равносильности групп 1–3 можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.

Равносильные преобразования используются для доказательства равносильностей , для приведения формул к заданному виду, для упрощения формул. Формула A считается проще равносильной ей формулы B , если она содержит меньше букв, меньше логических операций. При этом обычно операции эквивалентность и импликация заменяются операциями дизъюнкции и конъюнкции, а отрицание относят к элементарным высказываниям.

Определение 1. Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний

Важнейшие равносильности можно разбить на три группы:

I . Основные равносильности:

7. – закон противоречия.

8. – закон исключенного третьего.

9. – закон снятия двойного отрицания.

II . Равносильности, выражающие одни логические операции через другие:

III . Равносильности, выражающие основные законы алгебры логики:

1. – коммутативность конъюнкции.

2. – коммутативность дизъюнкции.

3. – ассоциативность конъюнкции.

4. – ассоциативность дизъюнкции.

5. – дистрибутивность конъюнкции относительно дизъюнкции.

6. – дистрибутивность дизъюнкции относительно конъюнкции.

Используя равносильности группы I , II и III , можно часть формул алгебры логики или всю формулу заменить равносильной ей формулой. Такие преобразования называются равносильными . Равносильные преобразования формул применяются для доказательства равносильностей , для приведения формул к заданному виду, для упрощения формул.

Пример 1. Доказать равносильность .

Решение . Для доказательства равносильности подвергнем ее левую часть равносильным преобразованиям: .

Определение 2. Формула А называется тождественно истинной (или тавтологией ), если она принимает значение 1 при всех значениях входящих в нее переменных.

Определение 3. Формула А называется тождественно ложной , если она принимает значение 0 при всех значениях входящих в нее переменных.

Пример 2 . Доказать тождественную истинность формулы:

Решение. Подвергнем формулу А равносильным преобразованиям

Для проверки усвоения теоретического материала можно перейти к выполнению Проверочной работы №2.

Упрощение логических выражений

Основная образовательная задача урока – научить учащихся умению упрощать логические выражения, правильно определять порядок выполнения операций в логическом выражении, устанавливать связи между различными частями сложных логических выражений, умение выбирать лучший вариант решения.

Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.

Обозначим: X – логическое высказывание, – инверсия, & – конъюнкция, – дизъюнкция, – импликация, – эквиваленция.

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

Представленные примеры демонстрируют основные приемы упрощения логических выражений.

Упростить логическое выражение:

Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций:

Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией.

Воспользуемся распределительным законом и вынесем за скобки общий множитель, затем операцией переменной с ее инверсией, затем операцией с константами.

Таким образом,

Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных дизъюнкцией. Сначала преобразуем выражения в скобках.

В первой скобке воспользуемся распределительным законом, во второй скобке – раскроем инверсию по правилу де Моргана и избавимся от инверсии по закону двойного отрицания.

Воспользуемся операцией переменной с ее инверсией.

Таким образом,

Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций. В выражении присутствуют два выражения в скобках, соединенных конъюнкцией. Сначала преобразуем выражения в скобках.

Раскроем инверсию по правилу де Моргана, избавимся от инверсии по закону двойного отрицания.

Воспользуемся переместительным законом и поменяем порядок логических сомножителей.

Применим закон склеивания

Воспользуемся распределительным законом, затем операцией переменной с ее инверсией, затем операцией с константами.

Таким образом,

Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

В выражении присутствует импликация. Сначала преобразуем импликацию .

Воспользуемся правилом де Моргана, затем законом двойного отрицания, затем раскроем скобки.

Применим закон идемпотенции и перегруппируем логические слагаемые.

Воспользуемся распределительным законом и вынесем за скобки общий логический множитель.

Воспользуемся операцией с константами.

Таким образом,

Рассмотрим 3 способа упрощения этого логического выражения.

1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией и законом идемпотенции.

Воспользуемся распределительным законом и раскроем скобки, затем операцией переменной с ее инверсией.

Воспользуемся законом идемпотенции.

Таким образом,

2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

Воспользуемся законом склеивания

Воспользуемся операцией переменной с ее инверсией.

Таким образом,

3 способ. Перепишем выражение с помощью более привычных операций умножения и сложения.

Повторим второй сомножитель , что разрешено законом идемпотенции.

Сгруппируем два первых и два последних сомножителя.

Воспользуемся законом склеивания

Таким образом,

Рассмотрим 2 способа упрощения этого логического выражения.

1 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

Воспользуемся распределительным законом и вынесем общий логический множитель за скобки.

2 способ. Перепишем выражение с помощью более привычных операций умножения и сложения, определимся с порядком выполнения операций.

Введем вспомогательный логический сомножитель

Сгруппируем 1 и 4, 2 и 3 логические слагаемые. Вынесем общие логические множители за скобки.

Воспользуемся операцией с константами и операцией переменной с ее инверсией.

Таким образом,

Получили два логических выражения:

Теперь построим таблицы истинности и посмотрим, правильно ли упрощено логическое выражение

X	Y	Z
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	1	0	1
1	0	0	1	0	0	1
1	0	1	1	0	1	1
1	1	0	0	0	0	0
1	1	1	0	0	1	1

X	Y	Z
0	0	0	1	0	0	0
0	0	1	1	0	0	0
0	1	0	0	0	0	0
0	1	1	1	0	1	1
1	0	0	1	1	0	1
1	0	1	1	1	0	1
1	1	0	0	0	0	0
1	1	1	1	1	0	1

X	Y	Z
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	0	0	0
0	1	1	0	1	1
1	0	0	1	0	1
1	0	1	1	0	1
1	1	0	0	0	0
1	1	1	0	1	1

X	Y	Z
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	0	0	0
0	1	1	1	1	1
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	0	0	0
1	1	1	1	1	1

Как видно из сравнения таблиц истинности формулы являются равносильными.

Законы алгебры логики. Упрощение логических выражений.

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

Большинство законов обеих алгебр схожи и уже знакомы вам. И лишь несколько вы узнаете впервые и, возможно, удивитесь.

Упрощение сложных высказываний — это замена их на равносильные на основе законов алгебры высказываний с целью получения высказываний более простой формы.

Нормальная форма выражений — это выражение где нет знаков операций импликации и эквивалентности, а инверсия применена только к отдельным высказываниям.

Для обрабатывания выражений вы должны свободно ориентироваться между обозначениями операций. Основные три из них имеют следующие варианты обозначений:

Инверсия (отрицание): Ø ,`A , не .

Конъюнкция (умножение): & , L , × .

Дизъюнкция (сложение): V, +.

Для удобства записи и большей наглядности можно записывать знаки операций в логических выражениях в более привычной нам форме: умножение — знаком ×, а сложение — знаком +.

Иначе говоря, упростить выражение — это найти в нём законы логики и их применить!

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

Итак, а теперь сами законы алгебры логики:

Чтобы ими пользоваться их надо знать, т.е. выучить. Но на самом деле эти законы во многом повторяю законы обычной алгебры.

Закон двойного отрицания напоминает нам ситуацию, когда «минус на минус даёт плюс», хотя так говорить и не грамотно, но зато именно так ученики его запоминают быстрее всего!

Законы исключения третьего, операции с константами и законы повторения следуют из определения самих логических операций сложения (дизъюнкции) и умножения (конъюнкции).

Переместительный, сочетательный и распределительный законы нам встречались и в обычной алгебре. Они и в алгебре логики работают точно так же! Правда распределительный закон относительно умножения на уроках математики применять никак нельзя, а в алгебре логики пожалуйста:

a + b × c = (a + b)× (a + c)

И последнее и самое интересное — это законы де Моргана (или двойного отрицания). Никак нельзя допускать при упрощении выражений оставлять знак отрицания более чем над одним высказыванием! С этой проблемой нам помогают бороться именно законы де Моргана.

Запомнить их просто: отрицание раздается каждому высказыванию, находящемуся под общей чертой, а знаки + меняются на × , и наоборот × на +.

Упрощение нескольких логических выражений представлено в следующем видео. Вы можете его ставить на паузу и сверяться с формулами законов в любом удобном для вас месте:

А теперь давайте проверим как вы поняли эту тему. Пройдите тест из шести вопросов.

Оценку узнаете в школе непосредственно у меня!

Упрощение ЛВ 2

Элементы математической логики — Практическое занятие №3 — Упрощение формул логики | Методическая разработка по теме:

По теме: методические разработки, презентации и конспекты

РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Среднее профессиональное образование по специальности 230111/Компьютерные сети

РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Среднее профессиональное образование по специальности 230111/Компьютерные сети…

Методическая разработка интегрированного урока по учебным дисциплинам «Элементы математической логики» и «Элементы высшей математики» преподавателей МКЭиИТ Невзоровой И.Б. и Сипачевой О.И.

Данная работа содержит методику проведения интегрированного урока по учебным дисциплинам «Элементы математической логики» и «Элементы высшей математики» для студентов 2 курса специальности 23011…

Элементы математической логики — Практическое занятие №2 — Составление таблиц истинности

Цель работы: закрепить основные понятия алгебры высказываний, отработать навыки составления таблицы истинности для высказываний, сформировать умения определять равносильность формул….

Элементы математической логики — Практическое занятие №4 — Приведение формул к совершенный нормальным формам

Цель практического занятия: закрепить знание о дизъюнктивной и конъюнктивной нормальных формах, сформировать умение приводить формулы алгебры логики к совершенной дизъюнктивной\конъюнктивной норм…

Практическая работа по дисциплине «Элементы математической логики»

Предназначена для студентов второго курса специальности 09.02.03…

Методические указания по выполнению практических работ по дисциплине «Элементы математической логики»

Практическая работа № 1 Определение значения логических функций и составления таблиц истинности сложных функций.Практическая работа № 2 Сравнение логических функций и определение их тождественнос…

Равносильные преобразования

§ 3 Равносильные преобразования

Определение 1. Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний

(АВ).

Важнейшие равносильности можно разбить на три группы:

I. Основные равносильности:

1. законы

2. идемпотентности.

7. — закон противоречия.

8. — закон исключенного третьего.

9. — закон снятия двойного отрицания.

10. законы

11. поглощения.

II. Равносильности, выражающие одни логические операции через другие:

3. законы

4. де Моргана.

III. Равносильности, выражающие основные законы алгебры логики:

1. — коммутативность конъюнкции.

2. — коммутативность дизъюнкции.

3. — ассоциативность конъюнкции.

4. — ассоциативность дизъюнкции.

5. — дистрибутивность конъюнкции относительно дизъюнкции.

6. — дистрибутивность дизъюнкции относительно конъюнкции.

Используя равносильности группы I, II и III, можно часть формул алгебры логики или всю формулу заменить равносильной ей формулой. Такие преобразования называются равносильными. Равносильные преобразования формул применяются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.

Пример 1. Доказать равносильность .

Решение. Для доказательства равносильности подвергнем ее левую часть равносильным преобразованиям: .

Определение 2. Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Определение 3. Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных.

Пример 2. Доказать тождественную истинность формулы:

Решение. Подвергнем формулу А равносильным преобразованиям

Для проверки усвоения теоретического материала можно перейти к выполнению Проверочной работы №2.

Равносильные преобразования и упрощения формул

Лабораторная работа № 2

Тема: «Алгебра высказываний»

Цель: Приобретение практических навыков работы с алгеброй логики высказываний.

2.1 . Теоретические сведения.

Таблицы истинности

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

Таблица истинности формулы алгебры высказываний содержит столько строк, сколько всевозможных наборов значений истинности переменных можно образовать. Так как каждая высказывательная переменная может принимать только два значения (0 и 1), то в случае переменных таблица истинности содержит строк.

При построении таблицы истинности наборы значений переменных располагают сверху вниз в лексикографическом порядке (каждый набор понимают как двоичную запись неотрицательного целого числа и располагают в порядке возрастания от (000 … 0) до (111 … 1).

Если у вас возникают трудности с использованием двоичной системы счисления, можно применять метод «последовательного половинного деления столбцов» – столбец первой переменной делят пополам и заполняют верхнюю половину нулями, а нижнюю половину – единицами, затем каждую половину второго столбца делят пополам и опять заполняют полученные половины нулями и единицами, и т. д. Затем в соответствии с порядком действий последовательно заполняют столбцы значений подформул, из которых образуется формула. Последним заполняется столбец значений истинности формулы.

Пример.Построить таблицу истинности формулы: .

1. Определить порядок действий в формуле:

1. Пользуясь определениями операций –, &, и , заполним таблицу:

Равносильные преобразования и упрощения формул

Ключом к решению примеров на равносильные преобразования и упрощения формул являются 19 основных равносильностей булевой алгебры высказывания, поэтому первым шагом при решении таких примеров является переход к булевым операциям с помощью формул:

~ .

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

Полезными при решении примеров на упрощение формул являются законы полупоглощения:

1) ; 1’) ;

2) ; 2’) ,

которые можно доказать.

► .

.◄

Пример.С помощью равносильных преобразований упростить формулу .

►

◄

Замечание.Любую запись а) — д) можно считать ответом.

Следующий тип параметров – доказательство равносильности двух заданных формул с помощью равносильных преобразований. Существует три основных схемы решения таких примеров. Каждая из них предполагает выполнение перехода к булевым операциям в исходных формулах.

Далее, по первой схеме предполагается, начиная с левой формулы, провести цепочку равносильных преобразований, завершив ее на правой формуле.

Вторая схема – зеркальное отражение первой.

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

Пример.Доказать, что .

►Перейдем к булевым операциям

1-я схема.

2-я схема

3-я схема

◄

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

(PDF) Минимизация конъюнктивных нормальных форм булевых функций комбинаторным методом

СИСТЕМЫ ИНФОРМАЦИИ И УПРАВЛЕНИЯ:

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

55 ТЕХНОЛОГИЧЕСКИЙ АУДИТ И ПРОИЗВОДСТВЕННЫЕ ЗАПИСИ — № 5/2 (43), 2018

Возможности. Возможностями дальнейшего исследования

комбинаторного метода может стать разработка

протокола вычисления минимальных функций для симметричных

булевых функций.

Дополнительные возможности для практической реализации

комбинаторного метода минимизации CNF

булевых функций заключаются в установлении новых критериев

комбинаторной оптимизации булевых функций, определяемых знаком минимальной функции и Boolean

минимизация функций по полной таблице истинности.

Угрозы. Процесс минимизации CNF булевых функций

комбинаторным методом не зависит от процессов минимизации

другими методами, поэтому

не представляет угрозы негативного воздействия на объект

исследования внешних факторов.

Аналогом комбинаторного метода минимизации

КНФ булевых функций является алгебраический метод [18].

Алгебраический метод минимизации КНФ булевых функций лучше всего тем, что для него созданы уже заданные законы

упрощения, обнаруженные свойства и алгоритмы

минимизации булевых функций. Однако

алгебраический метод — это словесная процедура для операционных

преобразований, которая в меньшей степени влияет на качество

минимизации по сравнению с образным преобразованием

комбинаторного метода.

8. Выводы

1. Установлено, что минимизация КНФ

булевых функций комбинаторным методом

основана на блок-схеме с повторением. Это таблица истинности

этой функции. Это позволяет сосредоточиться на принципе минимизации

в рамках протокола для вычисления

логической функции (в таблице истинности функции)

и, таким образом, отказаться от вспомогательных объектов, таких как карта Карно

, диаграммы Вейча. , ациклический граф, кубическое представление

и т. д.

2. Выявлено, что табличная организация математического аппарата

блок-схемы с повторением

позволяет получить больше информации об ортогональности, смежности

, уникальности блоков комбинаторной системы

и , следовательно, блоки таблицы истинности

этой функции. Эквивалентные образные преобразования по

своим свойствам обладают большой информационной емкостью, способной

заменить вербальные процедуры алгебраических преобразований, в частности

, используя библиотеку протоколов для минимизации

CNF булевых функций.

3. Выявлено, что образные преобразования

упрощают процедуру установления признаков минимальной логической функции

(примеры 8–10), что гарантирует оптимальное сокращение числа переменных

логики

функционировать без потери функциональности.

4. Выявлено, что для достижения наилучшего результата булевых

функций минимизация может быть получена в ДНФ и в КНФ минимальной функции

(примеры 6, 8–11).Из

следует, что минимизация данной функции должна быть

выполнена в двух нормальных формах — DNF и CNF, с использованием

полной таблицы истинности, а минимальная функция должна быть

, выбранной по результатам минимизации две нормальные формы

— DNF и CNF.

Литература

1. Ризник В.В., Соломко М.М. Минимизация булевых функций комбинаторным методом

// Технологический аудит и производство

Запасы.2017. Т. 4, выпуск 2 (36). С. 49–64. doi: http: //

doi.org/10.15587/2312-8372.2017.108532

2. Ризник В., Соломко М. Применение алгебраической операции суперприлипания

для минимизации булевых функций комбинаторным методом

// Технологический аудит и производственный

Запасы. 2017. Т. 6, выпуск 2 (38). С. 60–76. DOI: http: //

doi.org/10.15587/2312-8372.2017.118336

3.Ризнык В., Соломко М. Исследование протоколов мини-

мизации 5-битных булевых функций комбинаторным методом // Технологический аудит

и производственные резервы. 2018. Т. 4, выпуск 2 (42). С. 41–52.

doi: http://doi.org/10.15587/2312-8372.2018.140351

4. Cepek O., Kucera P., Savicky P. Булевы функции с простым сертификатом

для сложности CNF // Discrete Applied Mathe —

мат. 2012. Т. 160, выпуск 4-5. П.365–382. doi: http://doi.org/

10.1016 / j.dam.2011.05.013

5. Хемаспандра Э., Шнор Х. Минимизация для обобщенных

булевых формул // Труды двадцать второй статьи

международная совместная конференция по искусственному интеллекту. 2012.

С. 566–571.

6. Борос Э., Чепек О., Кучера П. Метод декомпозиции для доказательств минимальности CNF

// Теоретическая информатика. 2013. Т. 510.

П.111–126. doi: http://doi.org/10.1016/j.tcs.2013.09.016

7. Гурский С. Минимизация согласованных формул // WDS’11

Proceedings of Contributed Papers. Часть 1. 2011. С. 101–105.

8. Бернаскони А., Сириани В., Луччио Ф., Пагли Л. Трехуровневая логика

Минимизация

на основе закономерностей функций // IEEE Transac-

tions on Computer Aided Design of Integrated Circuits and

Systems . 2003. Vol. 22, вып.8.С. 1005–1016. doi: http: //

doi.org/10.1109/tcad.2003.814950

9. Носрати М., Карими Р. Алгоритм минимизации булевых функций

на основе Graph DS // World Applied Program-

ming . 2011. Т. 1, вып. 3. Р. 209–214.

10. Валли М., Периясами д-р Р., Амудхавел Дж. Состояние правил минимизации булевых функций

// Журнал

Advanced Research in Dynamics and Control Systems.2017.

Выпуск 12. С. 1322–1341. URL: http://www.jardcs.org/abstract.

php? Archiveid = 1323 #

11. Бояр Дж., Перальта Р. Новая минимальная комбинационная логика

Метод замещения с приложениями к криптологии. Лекция

Заметки по информатике. Берлин: Springer, 2010. С. 178–189.

doi: http://doi.org/10.1007/978-3-642-13193-6_16

12. Фисер П., Томан Д. Быстрый минимизатор SOP для логических функций

, описанный во многих терминах продукта // 2009 12-я конференция Euromicro

по проектированию цифровых систем, архитектурам, методам

и инструментам.Patras, 2009. doi: http://doi.org/10.1109/dsd.2009.157

13. Пынько А. П. Минимальные секвенциальные исчисления для монотонных цепных конечно-

значных логик // Вестник раздела логики. 2014. Т. 43,

Выпуск 1-2. С. 99–112.

14. Пынько А.П. Минимизация КНФ частично-монотонных бу-

левых функций // Доповіді Национальной академии наук Украины.

2017. Вып. 3. С. 18–21.

15. Булевы функции. URL: http: // любая-книга.org / download / 88296.html

16. Рыцарь Б.Е. Новый метод минимизации логических функций в полиномиальном теоретико-множественном формате

. 1. Обобщенные правила упрощения кон-

переходов // Управляющие системы и машины.

2015. Выпуск 2. С. 39–57. URL: http://dspace.nbuv.gov.ua/handle/

123456789/87194

17. Рыцарь Б.Е. Минимизация системы лохичных функций метод

паралельного розчепления конъюнктермив // Вісник Националь-

ноуниверситету «Львовская политехника».Радиоэлектроника

та телекомуникации. 2013. Выпуск 766. С. 18–27. URL: http: //

nbuv.gov.ua/UJRN/VNULPPT_2013_766_6

18. Мартынюк О. М. Основы дискретной математики. Конспект

лекции. Одесса: Одесский национальный политехнический университет:

Наука и техника, 2008. 300 с.

Ризник Владимир, д-р техн. Наук, профессор, кафедра автоматизированных систем управления

, Национальный университет «Львовская политехника»

, Украина, е-mail: rvv @ polynet.lviv.ua, ORCID: http: //

orcid.org/0000-0002-3880-4595

Соломко Михаил Александрович, кандидат технических наук, доцент кафедры компьютерной инженерии, Национальный университет воды и окружающей среды

Инжиниринг, Ровно, Украина, e-mail: [email protected], ORCID:

http://orcid.org/0000-0003-0168-5657

Propositional Logic

Раздел 3.1 Логика высказываний

Расследовать!

Вы наткнулись на двух троллей, играющих в Stratego®.Вам говорят:

Тролль 1: Если мы кузены, то мы оба лжецы.
Тролль 2: Мы кузены или оба лжецы.

Могли ли оба тролля быть рыцарями? Напомним, что все тролли либо всегда говорят правду рыцарей, либо всегда лгут.

Предложение — это просто утверждение. Логика высказываний изучает способы взаимодействия утверждений друг с другом. Важно помнить, что логика высказываний на самом деле не заботится о содержании утверждений.Например, с точки зрения логики высказываний утверждения «если луна сделана из сыра, то баскетбольные мячи — круглые» и «если у пауков восемь ног, то Сэм ходит прихрамывая». Они оба являются следствиями: утверждения формы \ (P \ imp Q \ text {.} \)

Подраздел Таблицы истинности

Вот вопрос об игре в Монополию:

Если вы получите больше удвоений, чем любой другой игрок, вы проиграете, а если проиграете, то вы, должно быть, купили больше всего собственности.

Верно или нет? Мы ответим на этот вопрос, и нам не нужно будет ничего знать о «Монополии». Вместо этого мы рассмотрим логическую форму заявления .

Нам нужно решить, когда утверждение \ ((P \ imp Q) \ vee (Q \ imp R) \) истинно. Используя определения связок в разделе 0.2, мы видим, что для того, чтобы это было истинным, либо \ (P \ imp Q \) должно быть истинным, либо \ (Q \ imp R \) должно быть истинным (или и то, и другое). Они истинны, если либо \ (P \) ложно, либо \ (Q \) истинно (в первом случае) и \ (Q \) ложно, либо \ (R \) истинно (во втором случае).Так что… да, становится немного запутанно. К счастью, мы можем составить диаграмму, чтобы отслеживать все возможности. Введите таблиц истинности . Идея такова: в каждой строке мы перечисляем возможные комбинации T и F (для истинного и ложного) для каждой из сентенциальных переменных, а затем отмечаем, является ли рассматриваемое утверждение истинным или ложным в этом случае. Мы делаем это для всех возможных комбинаций T и F. Тогда мы сможем ясно увидеть, в каких случаях утверждение истинно или ложно. Для сложных операторов мы сначала введем значения для каждой части оператора, чтобы разделить нашу задачу на более мелкие и более управляемые части.

Поскольку значение истинности утверждения полностью определяется значениями истинности его частей и тем, как они связаны, все, что вам действительно нужно знать, — это таблицы истинности для каждой логической связки. Вот они:

\ (П \)	\ (Q \)	\ (P \ клин Q \)
т	т	т
т	Ф	Ф
Ф.	т	Ф
Ф.	Ф	Ф

\ (П \)	\ (Q \)	\ (P \ vee Q \)
т	т	т
т	Ф	т
Ф.	т	т
Ф.	Ф	Ф

\ (П \)	\ (Q \)	\ (П \ имп Q \)
т	т	т
т	Ф	Ф
Ф.	т	т
Ф.	Ф	т

\ (П \)	\ (Q \)	\ (P \ iff Q \)
т	т	т
т	Ф	Ф
Ф.	т	Ф
Ф.	Ф	т

Таблица истинности отрицания выглядит так:

Ни одна из этих таблиц истинности не должна вызывать удивления; все они просто повторяют определения связок.Попробуем еще один.

Пример 3.1.1.

Составьте таблицу истинности для утверждения \ (\ neg P \ vee Q \ text {.} \)

Решение

Обратите внимание, что это утверждение не является \ (\ neg (P \ vee Q) \ text {,} \), отрицание принадлежит только \ (P \). Вот таблица истинности:

\ (П \)	\ (Q \)	\ (\ neg P \)	\ (\ neg P \ vee Q \)
т	т	Ф	т
т	Ф	Ф	Ф
Ф.	т	т	т
Ф.	Ф	т	т

Мы добавили столбец для \ (\ neg P \), чтобы упростить заполнение последнего столбца.Записи в столбце \ (\ neg P \) определялись записями в столбце \ (P \). Затем, чтобы заполнить последний столбец, посмотрите только на столбец для \ (Q \) и столбец для \ (\ neg P \) и используйте правило для \ (\ vee \ text {.} \)

Теперь давайте ответим на наш вопрос о монополии:

Пример 3.1.2.

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

Решение

Представьте утверждение символами как \ ((P \ imp Q) \ vee (Q \ imp R) \ text {,} \), где \ (P \) — это утверждение «вы получаете больше удвоений, чем любой другой игрок», \ (Q \) — это утверждение «вы потеряете», а \ (R \) — утверждение «вы, должно быть, купили больше всего собственности.«Теперь составьте таблицу истинности.

Таблица истинности должна содержать 8 строк, чтобы учесть все возможные комбинации истины и ложности среди трех утверждений. Вот полная таблица истинности:

\ (П \)	\ (Q \)	\ (R \)	\ (П \ имп Q \)	\ (Q \ имп R \)	\ ((П \ имп Q) \ vee (Q \ имп R) \)
т	т	т	т	т	т
т	т	Ф	т	Ф	т
т	Ф	т	Ф	т	т
т	Ф	Ф	Ф	т	т
Ф.	т	т	т	т	т
Ф.	т	Ф	т	Ф	т
Ф.	Ф	т	т	т	т
Ф.	Ф	Ф	т	т	т

Первые три столбца — это просто систематический список всех возможных комбинаций T и F для трех операторов (видите, как бы вы перечислили 16 возможных комбинаций для четырех операторов?).Следующие два столбца определяются значениями \ (P \ text {,} \) \ (Q \ text {,} \) и \ (R \) и определением импликации. Затем последний столбец определяется значениями в предыдущих двух столбцах и определением \ (\ vee \ text {.} \). Это последний столбец, о котором мы заботимся.

Обратите внимание, что в каждом из восьми возможных случаев рассматриваемое утверждение верно. Итак, наше утверждение о монополии верно (независимо от того, сколько собственности у вас есть, сколько удвоений вы выпустите, выиграете вы или проиграете).

Утверждение о монополии является примером тавтологии , утверждения, которое истинно только на основе своей логической формы. Тавтологии всегда верны, но они мало что говорят нам о мире. Никаких знаний о монополии не требовалось, чтобы определить, что это утверждение верно. Фактически, в равной степени верно и то, что «если луна сделана из сыра, тогда Элвис все еще жив, или если Элвис еще жив, то у единорогов 5 ног».

Подраздел Логическая эквивалентность

Вы могли заметить в примере 3.1.1, что последний столбец в таблице истинности для \ (\ neg P \ vee Q \) идентичен последнему столбцу в таблице истинности для \ (P \ imp Q \ text {:} \)

\ (П \)	\ (Q \)	\ (П \ имп Q \)	\ (\ neg P \ vee Q \)
т	т	т	т
т	Ф	Ф	Ф
Ф.	т	т	т
Ф.	Ф	т	т

Это говорит о том, что независимо от того, что такое \ (P \) и \ (Q \), утверждения \ (\ neg P \ vee Q \) и \ (P \ imp Q \) либо оба истинны, либо оба ложны.Поэтому мы говорим, что эти утверждения логически эквивалентны .

Логическая эквивалентность.

Два (молекулярных) утверждения \ (P \) и \ (Q \) логически эквивалентны при условии, что \ (P \) истинно именно тогда, когда \ (Q \) истинно. То есть \ (P \) и \ (Q \) имеют одинаковое значение истинности при любом присвоении значений истинности их атомарным частям.

Чтобы убедиться, что два оператора логически эквивалентны, вы можете составить таблицу истинности для каждого и проверить, идентичны ли столбцы для двух операторов.

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

Пример 3.1.3.

Являются ли утверждения «не будет дождя и снега» и «не будет дождя и не будет снега» логически эквивалентными?

Решение

Мы хотим знать, является ли \ (\ neg (P \ vee Q) \) логически эквивалентным \ (\ neg P \ wedge \ neg Q \ text {.} \) Составьте таблицу истинности, которая включает оба утверждения:

\ (П \)	\ (Q \)	\ (\ neg (P \ vee Q) \)	\ (\ нег П \ клин \ нег Q \)
т	т	Ф	Ф
т	Ф	Ф	Ф
Ф.	т	Ф	Ф
Ф.	Ф	т	т

Поскольку в каждой строке значения истинности для двух утверждений равны, эти два утверждения логически эквивалентны.

Обратите внимание, что этот пример дает нам способ «распределить» отрицание по дизъюнкции («или»). У нас есть аналогичное правило для распределения по союзу («и»):

Законы Де Моргана.

\ begin {уравнение *} \ neg (P \ wedge Q) \ text {логически эквивалентно} \ neg P \ vee \ neg Q \ text {.} \ end {уравнение *}

\ begin {уравнение *} \ neg (P \ vee Q) \ text {логически эквивалентно} \ neg P \ wedge \ neg Q \ text {.} \ end {уравнение *}

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

Законы Де Моргана не помогают нам напрямую с последствиями, но, как мы видели выше, каждое значение можно записать как дизъюнкцию:

Последствия — дизъюнкции.

\ begin {уравнение *} P \ imp Q \ text {логически эквивалентен} \ neg P \ vee Q \ text {.} \ end {уравнение *}

Пример: «Если число кратно 4, то оно четное» эквивалентно «число не кратно 4 или (иначе) четно.

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

Двойное отрицание.

\ begin {уравнение *} \ neg \ neg P \ text {логически эквивалентно} P \ text {.} \ end {уравнение *}

Пример: «Это не тот случай, когда \ (c \) не является нечетным» означает «\ (c \) нечетно.”

Давайте посмотрим, как мы можем применить эквивалентности, с которыми мы столкнулись до сих пор.

Пример 3.1.4.

Докажите, что утверждения \ (\ neg (P \ imp Q) \) и \ (P \ wedge \ neg Q \) логически эквивалентны без использования таблиц истинности.

Решение

Мы хотим начать с одного из операторов и преобразовать его в другое с помощью последовательности логически эквивалентных операторов. Начните с \ (\ neg (P \ imp Q) \ text {.} \) Мы можем переписать импликацию как дизъюнкцию, это логически эквивалентно

\ begin {уравнение *} \ Нег (\ Нег П \ Ви Q) \ текст {.} \ end {уравнение *}

Теперь примените закон ДеМоргана, чтобы получить

\ begin {уравнение *} \ neg \ neg P \ wedge \ neg Q \ text {.} \ end {уравнение *}

Наконец, используйте двойное отрицание, чтобы получить \ (P \ wedge \ neg Q \)

Обратите внимание, что приведенный выше пример показывает, что отрицание импликации НЕ является импликацией: это конъюнкция! Мы видели это раньше, в Разделе 0.2, но это настолько важно и полезно, что здесь стоит второй синий квадрат:

Отрицание следствия.

Отрицание импликации — это союз:

\ begin {уравнение *} \ neg (P \ imp Q) \ text {логически эквивалентно} P \ wedge \ neg Q \ text {.} \ end {уравнение *}

То есть, единственный способ, чтобы предположение было ложным, — это чтобы гипотеза была верной. И заключение было ложным.

Чтобы проверить, что два оператора логически эквивалентны, вы можете использовать таблицы истинности или последовательность логически эквивалентных замен. Метод таблицы истинности, хотя и громоздкий, имеет то преимущество, что он может проверить, что два оператора НЕ логически эквивалентны.

Пример 3.1.5.

Эквивалентны ли утверждения \ ((P \ vee Q) \ imp R \) и \ ((P \ imp R) \ vee (Q \ imp R) \)?

Решение

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

\ (П \)	\ (Q \)	\ (R \)	\ ((P \ vee Q) \ imp R \)	\ ((П \ имп R) \ vee (Q \ имп R) \)
т	т	т	т	т
т	т	Ф	Ф	Ф
т	Ф	т	т	т
т	Ф	Ф	Ф	т
Ф.	т	т	т	т
Ф.	т	Ф	Ф	т
Ф.	Ф	т	т	т
Ф.	Ф	Ф	т	т

Посмотрите на четвертый (или шестой) ряд.В этом случае \ ((P \ imp R) \ vee (Q \ imp R) \) истинно, но \ (((P \ vee Q) \ imp R \) ложно. Следовательно, эти утверждения не являются логически эквивалентными.

Хотя у нас нет логической эквивалентности, это случай, когда \ ((P \ vee Q) \ imp R \) истинно, так же как и \ ((P \ imp R) \ vee (Q \ imp R) \ text {.} \) Это говорит нам, что мы можем вывести \ ((P \ imp R) \ vee (Q \ imp R) \) из \ ((P \ vee Q) \ imp R \ text {, } \) только не в обратном направлении.

Подраздел Вычеты

Расследовать!

Холмс владеет двумя костюмами: черным и твидовым.Он всегда носит твидовый костюм или сандалии. Каждый раз, когда он надевает твидовый костюм и фиолетовую рубашку, он предпочитает не носить галстук. Он никогда не носит твидовый костюм, если он также не носит пурпурную рубашку или сандалии. Когда он носит сандалии, он также носит фиолетовую рубашку. Вчера Холмс надел галстук-бабочку. Что еще он носил?

Ранее мы утверждали, что следующий аргумент является допустимым:

Если Эдит съест свои овощи, то она может съесть печенье. Эдит съела свои овощи.Поэтому Эдит получает печенье.

Как мы узнаем, что это действительно так? Посмотрим на форму заявлений. Пусть \ (P \) означает «Эдит ест свои овощи», а \ (Q \) означает «Эдит может съесть печенье». Логическая форма аргумента:

	\ (П \ имп Q \)
	\ (П \)
\ (\ следовательно \)	\ (Q \)

Это пример правила вычета , форма аргумента, которая всегда действительна.Это особенно известное правило под названием modus ponens . Вы уверены, что это действующее правило вычета? Если нет, рассмотрите следующую таблицу истинности:

\ (П \)	\ (Q \)	\ (П \ имп Q \)
т	т	т
т	Ф	Ф
Ф.	т	т
Ф.	Ф	т

Это просто таблица истинности для \ (P \ imp Q \ text {,} \), но здесь важно то, что все строки в правиле дедукции имеют свой собственный столбец в таблице истинности.Помните, что аргумент действителен при условии, что вывод должен быть верным, если предположения верны. Предпосылки в этом случае: \ (P \ imp Q \) и \ (P \ text {.} \) Какие строк таблицы истинности соответствуют тому, что обе они истинны? \ (P \) истинно в первых двух строках, и из них только первая строка имеет истинное значение \ (P \ imp Q \). И, о чудо, в этом одном случае \ (Q \) также верно. Итак, если \ (P \ imp Q \) и \ (P \) оба истинны, мы видим, что \ (Q \) также должно быть истинным.

Вот еще несколько примеров.

Пример 3.1.6.

Покажите, что

	\ (П \ имп Q \)
	\ (\ нег П \ имп Q \)
\ (\ следовательно \)	\ (Q \)

— действительное правило вычета.

Решение

Мы составляем таблицу истинности, которая содержит все строки формы аргумента:

\ (П \)	\ (Q \)	\ (П \ имп Q \)	\ (\ neg P \)	\ (\ нег П \ имп Q \)
т	т	т	Ф	т
т	Ф	Ф	Ф	т
Ф.	т	т	т	т
Ф.	Ф	т	т	Ф

(мы включаем столбец для \ (\ neg P \) как шаг, чтобы помочь получить столбец для \ (\ neg P \ imp Q \)).

Теперь посмотрите на все строки, для которых истинны как \ (P \ imp Q \), так и \ (\ neg P \ imp Q \). Это происходит только в строках 1 и 3. Эй! В этих строках \ (Q \) также истинно, поэтому форма аргумента действительна (это действительное правило вывода).

Пример 3.1.7.

Решить, нужно ли

	\ (П \ имп R \)
	\ (Q \ имп R \)
	\ (R \)
\ (\ следовательно \)	\ (P \ vee Q \)

— действительное правило вычета.

Решение

Составим таблицу истинности, содержащую все четыре утверждения.

\ (П \)	\ (Q \)	\ (R \)	\ (П \ имп R \)	\ (Q \ имп R \)	\ (P \ vee Q \)
т	т	т	т	т	т
т	т	Ф	Ф	Ф	т
т	Ф	т	т	т	т
т	Ф	Ф	Ф	т	т
Ф.	т	т	т	т	т
Ф.	т	Ф	т	Ф	т
Ф.	Ф	т	т	т	Ф
Ф.	Ф	Ф	т	т	Ф

Посмотрите на предпоследний ряд.Здесь все три посылки аргумента верны, но вывод неверен. Таким образом, это неверное правило вычета.

Пока перед нами таблица истинности, посмотрите на строки 1, 3 и 5. Это единственные строки, в которых все утверждения \ (P \ imp R \ text {,} \) \ (Q \ imp R \ text {,} \) и \ (P \ vee Q \) верны. Также бывает, что \ (R \) истинно и в этих строках. Таким образом, мы открыли новое правило вычитания, которое, как мы знаем, действительно :

	\ (П \ имп R \)
	\ (Q \ имп R \)
	\ (P \ vee Q \)
\ (\ следовательно \)	\ (R \)

Подраздел за пределами предложений

Как мы видели в разделе 0.2, не каждое утверждение можно проанализировать, используя только логические связки. Например, мы можем захотеть работать с оператором:

Все простые числа больше 2 нечетны.

Чтобы записать это утверждение символически, мы должны использовать кванторы. Можно перевести так:

\ begin {уравнение *} \ forall x ((P (x) \ wedge x \ gt 2) \ imp O (x)) \ text {.} \ end {уравнение *}

В этом случае мы используем \ (P (x) \) для обозначения «\ (x \) простое» и \ (O (x) \) для обозначения «\ (x \) нечетное.Это не предложения, поскольку их значение истинности зависит от ввода \ (x \ text {.} \). Лучше думать о \ (P \) и \ (O \) как об обозначении свойств их ввода. Технический термин для них — предикатов , и когда мы изучаем их логически, нам нужно использовать логику предикатов .

Важно подчеркнуть, что логика предикатов расширяет логику высказываний (во многом так же, как квантовая механика расширяет классическую механику). Вы заметите, что в нашем утверждении выше по-прежнему используются (пропозициональные) логические связки.Все, что мы узнали о логической эквивалентности и выводах, по-прежнему применимо. Однако логика предикатов позволяет нам анализировать утверждения с более высоким разрешением, копаясь в отдельных предложениях \ (P \ text {,} \) \ (Q \ text {,} \) и т. Д.

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

Пример 3.1.8.

Предположим, мы утверждаем, что не существует наименьшего числа. Мы можем перевести это в символы как

\ begin {уравнение *} \ Neg \ существует x \ forall y (x \ le y) \ end {уравнение *}

(буквально: «неверно, что существует такое число \ (x \), что для всех чисел \ (y \ text {,} \) \ (x \) меньше или равно \ (y \) »).

Однако мы знаем, как отрицание взаимодействует с кванторами: мы можем передать отрицание квантору, переключая тип квантора (между универсальным и экзистенциальным).Таким образом, приведенное выше утверждение должно быть , логически эквивалентным от до

\ begin {уравнение *} \ forall x \ существует y (y \ lt x) \ text {.} \ end {уравнение *}

Обратите внимание, что \ (y \ lt x \) является отрицанием \ (x \ le y \ text {.} \). Это буквально говорит: «Для каждого числа \ (x \) есть число \ (y \) который меньше, чем \ (x \ text {.} \) ». Мы видим, что это еще один способ сделать наше первоначальное утверждение.

Пример 3.1.9.

Можно ли изменить порядок квантификаторов? Например, рассмотрим два утверждения:

\ begin {уравнение *} \ forall x \ существует y P (x, y) \ qquad \ mathrm {и} \ qquad \ exists y \ forall x P (x, y) \ text {.} \ end {уравнение *}

Являются ли они логически эквивалентными?

Решение

Эти утверждения логически НЕ эквивалентны. Чтобы увидеть это, мы должны предоставить интерпретацию предиката \ (P (x, y) \), которая делает одно из утверждений истинным, а другое ложным.

Пусть \ (P (x, y) \) будет предикатом \ (x \ lt y \ text {.} \) Верно, что в натуральных числах для всех \ (x \) существует некоторое \ ( у \) больше, чем \ (х \) (поскольку чисел бесконечно много). Однако не существует натурального числа \ (y \), которое больше любого числа \ (x \ text {.} \) Таким образом, \ (\ forall x \ exists y P (x, y) \) может быть истинным, в то время как \ (\ exists y \ forall x P (x, y) \) ложно.

Однако мы не можем сделать обратное. Если существует некоторый \ (y \), для которого каждое \ (x \) удовлетворяет \ (P (x, y) \ text {,} \), то, безусловно, для каждого \ (x \) существует некоторый \ (y \) который удовлетворяет \ (P (x, y) \ text {.} \) Первый говорит, что мы можем найти один \ (y \), который работает для каждого \ (x \ text {.} \) Второй допускает разные \ ( y \) работают для разных \ (x \), но ничто не мешает нам использовать те же \ (y \), которые работают для каждого \ (x \ text {.} \) Другими словами, хотя у нас нет логической эквивалентности между двумя утверждениями, у нас есть действующее правило вывода:

	\ (\ существует y \ forall x P (x, y) \)
\ (\ следовательно \)	\ (\ forall x \ существует y P (x, y) \)

Другими словами, это означает, что единственный оператор

\ begin {уравнение *} \ существует y \ forall x P (x, y) \ imp \ forall x \ exists y P (x, y) \ end {уравнение *}

всегда верно.Это своего рода тавтология, хотя мы оставляем за собой этот термин для обозначения необходимых истин в логике высказываний. Утверждение логики предикатов, которое обязательно истинно, получает более престижное обозначение закона логики (или иногда логически действительного , но это менее забавно).

Упражнения Упражнения

1.

Рассмотрим высказывание о вечеринке: «Если у вас день рождения или будет торт, значит, будет торт».

Переведите приведенное выше утверждение в символы.Ясно укажите, какой оператор является \ (P \), а какой — \ (Q \ text {.} \)
Составьте таблицу истинности для утверждения.
Если предположить, что утверждение верно, что (если вообще что-нибудь) вы можете сделать вывод, будет ли торт?
Если предположить, что утверждение верно, то какой (если что-нибудь) вы можете сделать вывод, если торта не будет?
Предположим, вы узнали, что заявление было ложью. Какие выводы можно сделать?

Решение

\ (P \ text {:} \) это ваш день рождения; \ (Q \ text {:} \) будет торт.\ ((P \ vee Q) \ imp Q \)
Подсказка: вы должны получить три буквы Т и одну F.
Только то, что там будет торт.
Это НЕ твой день рождения!
Это твой день рождения, но торт — ложь.

2.

Составьте таблицу истинности для утверждения \ ((P \ vee Q) \ imp (P \ wedge Q) \ text {.} \)

Решение

\ (P \)	\ (Q \)	\ ((P \ vee Q) \ imp (P \ клин Q) \)
т	т	т
т	Ф	Ф
Ф.	т	Ф
Ф.	Ф	т

3.

Составьте таблицу истинности для утверждения \ (\ neg P \ wedge (Q \ imp P) \ text {.} \) Что вы можете сделать в отношении \ (P \) и \ (Q \), если вы знаете, что утверждение правда?

Решение

\ (П \)	\ (Q \)	\ (\ neg P \ клин (Q \ imp P) \)
т	т	Ф
т	Ф	Ф
Ф.	т	Ф
Ф.	Ф	т

Если утверждение верно, то и \ (P \), и \ (Q \) ложны.

4.

Составьте таблицу истинности для утверждения \ (\ neg P \ imp (Q \ wedge R) \ text {.} \)

Подсказка

Как и выше, только теперь вам понадобится 8 рядов вместо 4.

5.

Джефф Пошингтен выходит в модную пиццерию и решает заказать кальцоне. Когда официант спрашивает, что бы он хотел, он отвечает: «Я хочу пепперони или колбасу. Кроме того, если у меня есть колбаса, то я должен включить еще и перепелов. Да, и если у меня есть пепперони или перепела, то мне также нужен сыр рикотта.”

Переведите приказ Джеффа в логические символы.
Официант знает, что Джефф либо лжец, либо говорит правду (так что либо все, что он говорит, либо ложь, либо все правда). Что он?
Что может сделать официант по поводу ингредиентов кальцоне, желаемого Джеффом?

Намекать

Вы должны записать три утверждения, используя символы \ (P, Q, R, S \ text {.} \). Если Джефф говорит правду, то все три утверждения будут верными.Если бы он был лжецом, то все три утверждения были бы ложными. Но в любом случае мы еще не знаем, истинны или ложны четыре атомарных утверждения, поскольку он не сказал их сами по себе.

Таблица истинности может помочь, хотя, вероятно, не совсем необходима.

6.

Определите, являются ли следующие два утверждения логически эквивалентными: \ (\ neg (P \ imp Q) \) и \ (P \ wedge \ neg Q \ text {.} \). Объясните, откуда вы знаете, что вы правы.

Решение

Составьте таблицу истинности для каждого и сравните.Эти утверждения логически эквивалентны.

7.

Эквивалентны ли утверждения \ (P \ imp (Q \ vee R) \) и \ ((P \ imp Q) \ vee (P \ imp R) \)?

8.

Упростите следующие утверждения (чтобы отрицание появлялось только непосредственно перед переменными).

\ (\ neg (P \ imp \ neg Q) \ text {.} \)
\ ((\ neg P \ vee \ neg Q) \ imp \ neg (\ neg Q \ wedge R) \ text {.} \)
\ (\ neg ((P \ imp \ neg Q) \ vee \ neg (R \ wedge \ neg R)) \ text {.} \)
Неверно, что если Сэм не мужчина, то Крис — женщина, а Крис — не женщина.

Решение

\ (P \ wedge Q \ text {.} \)
\ ((\ neg P \ vee \ neg R) \ imp (Q \ vee \ neg R) \) или, сначала заменив импликацию дизъюнкцией: \ ((P \ wedge Q) \ vee (Q \ vee \ негр R) \ text {.} \)
\ ((P \ wedge Q) \ wedge (R \ wedge \ neg R) \ text {.} \) Это обязательно неверно, поэтому оно также эквивалентно \ (P \ wedge \ neg P \ text {. } \)
Либо Сэм — женщина, а Крис — мужчина, либо Крис — женщина.

9.

Используйте законы Де Моргана и любые другие известные вам факты логической эквивалентности, чтобы упростить следующие утверждения. Покажи все свои шаги. В ваших заключительных утверждениях отрицания должны появляться только непосредственно рядом с переменными предложения или предикатами (\ (P \ text {,} \) \ (Q \ text {,} \) \ (E (x) \ text {,} \) и т. д.), и никаких двойных отрицаний. Было бы неплохо использовать только союзы, дизъюнкции и отрицания.

\ (\ neg ((\ neg P \ wedge Q) \ vee \ neg (R \ vee \ neg S)) \ text {.} \)
\ (\ neg ((\ neg P \ imp \ neg Q) \ wedge (\ neg Q \ imp R)) \) (осторожно с последствиями).
Для обеих приведенных выше частей проверьте правильность ответов с помощью таблиц истинности. То есть используйте таблицу истинности, чтобы проверить, что данное утверждение и предлагаемое вами упрощение фактически логически эквивалентны.

10.

Рассмотрим утверждение: «Если число треугольное или квадратное, то оно не простое»

Составьте таблицу истинности для утверждения \ ((T \ vee S) \ imp \ neg P \ text {.} \)
Если вы считаете, что утверждение ложно , какими свойствами должен обладать контрпример? Объясните, ссылаясь на вашу таблицу истинности.
Если бы утверждение было правдой, какой бы вы могли сделать вывод о числе 5657, которое определенно простое? Опять же, объясните, используя таблицу истинности.

Подсказка

Будет три строки, в которых утверждение ложно.
Рассмотрим три строки, которые оцениваются как ложь, и говорят, какие истинные значения для \ (T \ text {,} \) \ (S \ text {,} \) и \ (P \) присутствуют.
Вы ищете строку, в которой \ (P \) истинно, а все утверждение истинно.

11.

Томми Фланаган рассказывал вам, что он ел вчера днем. Он говорит вам: «Я ел либо попкорн, либо изюм. Кроме того, если у меня были бутерброды с огурцами, то у меня была газировка. Но я не пил газировку или чай ». Конечно, вы знаете, что Томми — худший лжец в мире, и все, что он говорит, — ложь. Что ел Томми?

Обоснуйте свой ответ, записав все утверждения Томми с использованием переменных предложения (\ (P, Q, R, S, T \)), взяв их отрицания и используя их, чтобы вывести, что на самом деле ел Томми.

Подсказка

Запишите три утверждения, а затем возьмите отрицание каждого (поскольку он лжец). Вы должны обнаружить, что Томми съел одно блюдо и выпил одно. (\ (Q \) для бутербродов с огурцами.)

12.

Определите, действительно ли следующее правило вычета:

	\ (P \ vee Q \)
	\ (\ neg P \)
\ (\ следовательно \)	\ (Q \)

Решение

Правило вычета действительно.Чтобы убедиться в этом, составьте таблицу истинности, которая содержит \ (P \ vee Q \) и \ (\ neg P \) (и, конечно, \ (P \) и \ (Q \)). Посмотрите на значение истинности \ (Q \) в каждой из строк, в которых есть \ (P \ vee Q \) и \ (\ neg P \) true.

13.

Определите, является ли следующее действительным правилом вычета:

	\ (П \ имп (Q \ vee R) \)
	\ (\ нег (П \ имп Q) \)
\ (\ следовательно \)	\ (R \)

14.

Определите, является ли следующее действительным правилом вычета:

	\ ((P \ клин Q) \ имп R \)
	\ (\ neg P \ vee \ neg Q \)
\ (\ следовательно \)	\ (\ отрицательный R \)

15.

Можете ли вы связать последствия вместе? То есть, если \ (P \ imp Q \) и \ (Q \ imp R \ text {,} \) означает, что это означает \ (P \ imp R \ text {?} \). Можете ли вы связать вместе другие импликации? Выясним:

Докажите, что следующее действительное правило вычета:
\ (П \ имп Q \)
\ (Q \ имп R \)
\ (\ следовательно \) \ (П \ имп R \)

Докажите, что следующее действительное правило вычета для любого \ (n \ ge 2 \ text {:} \)

\ (P_1 \ имп P_2 \)

\ (P_2 \ имп P_3 \)

\ (\ vdots \)

\ (P_ {n-1} \ imp P_n \)

\ (\ следовательно \)

\ (P_1 \ imp P_n \ text {.n \) строка таблицы истинности. Вместо этого вы должны использовать часть (а) и математическую индукцию.

Подсказка

Для второй части вы можете индуктивно предположить, что из первого \ (n-2 \) импликации вы можете вывести \ (P_1 \ imp P_ {n-1} \ text {.} \). Затем вы вернулись в дело в части (а) снова.

16.

Мы также можем упростить утверждения в логике предикатов, используя наши правила передачи отрицаний кванторам, а затем применяя пропозициональную логическую эквивалентность к «внутренней» пропозициональной части.Упростите приведенные ниже утверждения (чтобы отрицание появлялось только непосредственно рядом с предикатами).

\ (\ neg \ exists x \ forall y (\ neg O (x) \ vee E (y)) \ text {.} \)
\ (\ neg \ forall x \ neg \ forall y \ neg (x \ lt y \ wedge \ exists z (x \ lt z \ vee y \ lt z)) \ text {.} \)
Существует число \ (n \), для которого никакое другое число не меньше \ (n \), чем или равно \ (n \ text {.} \)
Неверно, что для каждого числа \ (n \) есть два других числа, между которыми находится \ (n \).

Решение

\ (\ forall x \ exists y (O (x) \ wedge \ neg E (y)) \ text {.} \)
\ (\ существует x \ forall y (x \ ge y \ vee \ forall z (x \ ge z \ wedge y \ ge z)) \ text {.} \)
Существует число \ (n \), для которого любое другое число строго больше, чем \ (n \ text {.} \)
Есть число \ (n \), которого нет между двумя другими числами.

17.

Упростите приведенные ниже утверждения до такой степени, что символы отрицания встречаются только непосредственно рядом с предикатами.

\ (\ neg \ forall x \ forall y (x \ lt y \ vee y \ lt x) \ text {.} \)
\ (\ neg (\ exists x P (x) \ imp \ forall y P (y)) \ text {.} \)

18,

Упрощение отрицаний будет особенно полезно в следующем разделе, когда мы попытаемся доказать утверждение, рассмотрев, что произошло бы, если бы оно было ложным. Для каждого утверждения ниже, как можно проще, напишите отрицание утверждения. Не говорите просто: «Это неправда…».

Каждое число четное или нечетное.
Существует арифметическая и геометрическая последовательность.
Для всех чисел \ (n \ text {,} \), если \ (n \) простое, то \ (n + 3 \) не является простым.

Подсказка

Может помочь перевести утверждения в символы, а затем использовать формульные правила для упрощения отрицаний (то есть правила для кванторов и законы Де Моргана). После упрощения вы должны получить, например, \ (\ forall x (\ neg E (x) \ wedge \ neg O (x)) \ text {,} \).Затем переведите это обратно на английский.

19.

Предположим, что \ (P \) и \ (Q \) — (возможно, молекулярные) пропозициональные утверждения. Докажите, что \ (P \) и \ (Q \) логически эквивалентны, если они есть, только если \ (P \ тогда и только тогда, когда Q \) — тавтология.

Подсказка

Что означают эти концепции в терминах таблиц истинности?

20.

Предположим, что \ (P_1, P_2, \ ldots, P_n \) и \ (Q \) являются (возможно, молекулярными) пропозициональными утверждениями. Предположим далее, что

	\ (P_1 \)
	\ (P_2 \)
	\ (\ vdots \)
	\ (П_н \)
\ (\ следовательно \)	\ (Q \)

— действительное правило вычета.Докажите, что утверждение

\ begin {уравнение *} (P_1 \ клин P_2 \ клин \ cdots \ клин P_n) \ imp Q \ end {уравнение *}

— это тавтология.

Логическая эквивалентность — обзор

5.1 Ядерные и внеядерные свойства

Различие между ядерными и внеядерными свойствами представлено в обозначениях как различие между ‘ P ‘ и ‘P !’ предикаты. Ссылка на ядерные или внеядерные свойства безразлично обозначается восклицательным знаком в круглых скобках: « P (!)».Количественная оценка ядерных или внеядерных свойств обозначается выражениями вида:

… (∀x)… (∀Pn (!))… (… Pn (!)) X1,…, xn…)…

Предсказания: только по внешнему виду высшего порядка. Логика неупорядочена по типам, и предложения такого рода являются примерами ограниченной квантификации, удобными сокращениями для более явно неупорядоченного по типу выражения… (∀ x )… (∀ y (!))… (… y (!) x …)… Выравнивание типов уместно в мейнонгианской логике, потому что свойства, подобные всему, что можно придумать, также являются преднамеренными объектами.

Ядерная P свойства и внеядерная P ! свойства различаются по следующим критериям:

(C1) — (∀x1)… (∀xn) (∀Pn) (- Pnx1,…, xn≡Pn¯x1,…, xn)

(C2) (∀ x1)… (∀xn) (∀Pn!) (- Pn! x1,…, xn≡Pn¯! x1,…, xn)

Их также можно назвать критериями отрицания / двойного дополнения для ядерно-экстраядерных разграничение собственности. Достаточно полагаться исключительно на (C1) или (C2), классифицируя внеядерные свойства как свойства, которые не удовлетворяют (C1), или ядерные свойства как свойства, которые не удовлетворяют (C2).

Критерии отмечают важное различие между ядерными и внеядерными свойствами. Пары ядерного свойства и дополнения свойств могут не удерживать неполные или неопределенные несуществующие объекты. Золотая гора Джорджа Беркли (чтобы проиллюстрировать знакомый пример) не выше и не выше горы Рене Домаля. Аналог. Критерий (C1) отражает тот факт, что свойство быть выше Mt. Аналог является ядерным, а не экстраядерным, поскольку отрицает логическую эквивалентность отрицания предложения и выражений-двойников дополнения ядерных предикатов.Сказать, что круглый квадрат неквадратный (потому что он круглый) — это , а не , чтобы сказать, что круглый квадрат не является квадратом (поскольку согласно тезису независимости он является одновременно круглым и квадратом). ⁶

Экстраядерные свойства, напротив, не допускают такой широты, даже когда предполагается несуществующие неполные, неопределенные или невозможные объекты. Объект, детерминированный или неопределенный, либо существует, либо не существует, возможен или невозможен, самотождественен или не самотождественен, без промежуточной основы или места для внеядерной неполноты или неопределенности.Это означает, как фактически требует (C2), что экстраядерные эквиваленты дополнения предиката и отрицания предложения логически эквивалентны и взаимозаменяемы в экстенсиональном плане. По этой причине внеядерная подтеория мейнонгианской логики, в отличие от объектной теории ядерных предсказаний, классически бивалентна. Ядерные конститутивные свойства принадлежат отличительным или уникально индивидуальным Sosein преднамеренного объекта, при абсолютном исключении внеядерных свойств.

Критерии (C1) и (C2) сами по себе не определяют, какие свойства являются ядерными, а какие внеядерными. Критерии устанавливают отличительные черты двух типов свойств и в приложении требуют дополнительной информации о том, является ли дополнение определенного свойства, предопределенного для объекта, логически эквивалентным его аналогу отрицания предложения. Может быть предоставлен независимый неформальный критерий различия, чтобы интуитивно определить, какие свойства удовлетворяют (C1), а не (C2), а какие (C2), а не (C1).Свойство является внеядерным в этой концепции тогда и только тогда, когда оно может быть определено только в терминах логических операторов и неинтерпретируемых предикатных символов. Он ядерный тогда и только тогда, когда он не является внеядерным, или если он не определяется таким образом, но требует для своего определения интерпретации по крайней мере некоторых предикатных символов.

Логические эквиваленты

Раздел 2.1 Логические эквивалентности

Определение 2.1.1.

Выражение, включающее логические переменные, истинное для всех значений, называется тавтологией .

Определение 2.1.2.

Выражение, включающее логические переменные, ложное для всех значений, называется противоречием .

Утверждения, не являющиеся тавтологиями или противоречиями, называются условными обстоятельствами .

Определение 2.1.3.

Мы говорим, что два предложения \ (p \) и \ (q \) логически эквивалентны , если \ (p \ leftrightarrow q \) — тавтология. Обозначим это \ (p \ Equiv q \ text {.} \)

Пример 2.1.4.

Докажите, что следующие утверждения эквивалентны, используя таблицу истинности.

\ (\ Displaystyle (\ отр р \ к (д \ клин \ отр д)) \ экв р \)
\ (\ Displaystyle п \ ви (п \ клин д) \ экв р \)
\ (\ Displaystyle п \ Ви (д \ клин г) \ эквив (п \ Ви д) \ клин (р \ Ви г) \)
\ (\ Displaystyle \ neg (п \ к q) \ эквив р \ клин \ neg q \)
\ (\ Displaystyle р \ к д \ эквив \ нег р \ ви д \)

Видео / Ответ Решение Вот решение для \ ((\ neg p \ to (q \ wedge \ neg q)) \ Equiv p \ text {:} \) Таблица 2.1.6. Отображение \ ((\ neg p \ to (q \ wedge \ neg q)) \ leftrightarrow p \) является тавтологией

\ (p \)	\ (д \)	\ (\ neg p \)	\ (д \ клин \ отр д \)	\ (\ отр р \ к (д \ клин \ отр д) \)	\ ((\ neg p \ to (q \ клин \ neg q)) \ leftrightarrow p \)
т	т	Ф	Ф	т	Т
т	Ф	Ф	Ф	т	Т
Ф.	т	т	Ф	Ф	Т
Ф.	Ф	т	Ф	Ф	Т

Таблица 2.1.8. Логические эквиваленты

	Коммутативные законы
\ (п \ lor q \ эквив q \ lor p \)		\ (п \ земля q \ эквив q \ земля п \)
	Ассоциативные законы
\ ((p \ lor q) \ lor r \ Equiv p \ lor (q \ lor r) \)		(\ (p \ земля q) \ земля r \ эквив p \ земля (q \ земля r) \)
	Распределительные законы
\ (п \ земля (q \ lor r) \ эквив (p \ land q) \ lor (p \ land r) \)		\ (п \ лор (д \ земля г) \ экв (п \ лор д) \ земля (п \ лор г) \)
	Законы о личности
\ (p \ lor F \ Equiv p \)		\ (п \ земля Т \ экв п \)
	Законы об отрицании
\ (п \ земля \ негр \ эквив F \)		\ (п \ лор \ негр \ эквив Т \)
	Идемпотентные законы
\ (п \ лор п \ эквив)		\ (п \ земля п \ эквив п \)
	Законы о господстве
\ (п \ земля F \ эквив F \)		\ (п \ лор Т \ эквив Т \)
	Законы поглощения
\ (п \ земля (п \ лор q) \ эквив п \)		\ (п \ лор (п \ земля q) \ эквив р \)
	Законы ДеМоргана
\ (\ neg (p \ lor q) \ Equ (\ neg p) \ land (\ neg q) \)		\ (\ нег (п \ земля д) \ экв (\ нег р) \ лор (\ нег д) \)
	Закон о двойном отрицании
	\ (\ нег (\ нег р) \ экв р \)
	Последствия
	\ (п \ к д \ эквив \ нег р \ лор д \)

Пример 2.1.9.

Используйте существующие логические эквиваленты из Таблицы 2.1.8, чтобы показать, что следующие эквивалентны.

\ (\ Displaystyle п \ клин д \ эквив \ нег (п \ к \ нег д) \)
\ (\ Displaystyle (п \ к г) \ ви (д \ к г) \ эквив (п \ клин д) \ к г \)
\ (\ Displaystyle д \ к п \ эквив \ отр р \ к \ отр q \)
\ (\ Displaystyle (\ отр р \ к (д \ клин \ отр д)) \ экв р \)

Упражнения 2.1.1 Упражнения

1.

Определите, являются ли следующие два оператора логически эквивалентными: \ (\ neg (p \ to q) \) и \ (p \ wedge \ neg q \ text {.} \) Объясните, откуда вы знаете, что правы.

Решение

Составьте таблицу истинности для каждого и сравните. Эти утверждения логически эквивалентны.

2.

Являются ли утверждения \ (p \ to (q \ vee r) \) и \ ((p \ to q) \ vee (p \ to r) \) логически эквивалентными?

Решение

Давайте начнем с левой стороны и продолжим движение вправо, чтобы выяснить это.

\ begin {align *} p \ to (q \ vee r) \ amp \ Equiv \ neg p \ lor (q \ land r) \\ \ amp \ Equiv (\ neg p \ land q) \ lor (\ neg p \ land r) \\ \ amp \ Equiv (p \ to q) \ lor (p \ to r) \ end {выровнять *}

, что мы и хотели показать.

3.

Используйте таблицу истинности, чтобы показать, что \ ((p \ to q) \ land (p \ to r) \) и \ (p \ to (q \ land r) \) логически эквивалентны.

Решение

Вот альтернативное решение, использующее предыдущие эквивалентности (не таблицу истинности):

\ begin {align *} (p \ to q) \ land (p \ to r) & \ Equiv (\ neg p \ lor q) \ land (\ neg p \ lor r) \\ & \ эквив \ нег р \ лор (д \ земля г) \\ & \ Equiv p \ to (q \ land r) \ end {выровнять *}

4.

Упростите следующие утверждения (чтобы отрицание появлялось только непосредственно перед переменными).

\ (\ neg (p \ to \ neg q) \ text {.} \)
\ ((\ neg p \ vee \ neg q) \ to \ neg (\ neg q \ wedge r) \ text {.} \)
\ (\ neg ((p \ to \ neg q) \ vee \ neg (r \ wedge \ neg r)) \ text {.} \)

Видео / ответ

\ (p \ wedge q \ text {.} \)
\ ((\ neg p \ vee \ neg r) \ to (q \ vee \ neg r) \) или, сначала заменив импликацию дизъюнкцией: \ ((p \ wedge q) \ vee (q \ vee \ негр) \ текст {.} \)
\ ((p \ wedge q) \ wedge (r \ wedge \ neg r) \ text {.} \) Это обязательно неверно, поэтому оно также эквивалентно \ (p \ wedge \ neg p \ text {.} \)
Либо Сэм не мужчина, а Крис не женщина, либо Крис женщина.

5.

Используйте законы Де Моргана и любые другие известные вам факты логической эквивалентности, чтобы упростить следующие утверждения. Покажи все свои шаги. В ваших заключительных утверждениях отрицания должны появляться только непосредственно рядом с переменными предложения или предикатами (\ (p \ text {,} \) \ (q \ text {,} \) и т. Д.), И никаких двойных отрицаний. Было бы неплохо использовать только союзы, дизъюнкции и отрицания.

\ (\ neg ((\ neg p \ wedge q) \ vee \ neg (r \ vee \ neg s)) \ text {.} \)
\ (\ neg ((\ neg p \ to \ neg q) \ wedge (\ neg q \ to k)) \) (осторожно с последствиями).
\ (\ Displaystyle (п \ земля д) \ к (п \ лор д) \)

Решение

\ begin {align *} \ neg ((\ neg p \ wedge q) \ vee \ neg (r \ vee \ neg s)) \ amp \ Equiv \ neg (\ neg p \ wedge q) \ land \ neg \ neg (r \ vee \ neg с) \\ \ amp \ Equiv \ neg (\ neg p \ wedge q) \ land (r \ vee \ neg s) \\ \ amp \ Equiv (\ neg \ neg p \ lor \ neg q) \ land (r \ lor \ neg s) \\ \ amp \ эквив (п \ лор \ нег q) \ земля (г \ лор \ нег с) \ end {выровнять *}
\ begin {align *} \ neg ((\ neg p \ to \ neg q) \ wedge (\ neg q \ to k)) \ amp \ Equiv \ neg ((\ neg \ neg p \ lor \ neg q) \ wedge (\ neg \ neg д \ л или к)) \\ \ amp \ Equiv \ neg ((p \ lor \ neg q) \ wedge (q \ lor k)) \\ \ amp \ Equiv \ neg (p \ lor \ neg q) \ lor \ neg (q \ lor k) \\ \ amp \ Equiv (\ neg p \ land \ neg \ neg q) \ lor (\ neg q \ land \ neg k) \\ \ amp \ эквив (\ нег р \ земля д) \ лор (\ нег д \ земля \ нег к) \ end {выровнять *}
\ begin {align *} (p \ land q) \ to (p \ lor q) \ amp \ Equiv \ neg (p \ land q) \ lor (p \ lor q) \\ \ amp \ Equiv (\ neg p \ lor \ neg q) \ lor (p \ lor q) \\ \ amp \ Equiv \ neg p \ lor \ neg q \ lor p \ lor q \\ \ amp \ Equiv \ neg p \ lor p \ lor \ neg q \ lor q \\ \ amp \ Equiv (\ neg p \ lor p) \ lor (\ neg q \ lor q) \\ \ amp \ Equiv (T) \ lor (T) \\ \ amp \ эквив Т \ end {выровнять *}
… это тавтология!

Подраздел 2.1.2 Сообщения форума об этом разделе

Математика | Эквивалентность высказываний — GeeksforGeeks

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

Типы предложений, основанных на ценностях истинности

Тавтология — Положение, которое всегда истинно, называется тавтологией.
Противоречие. Утверждение, которое всегда неверно, называется противоречием.
Случайность — предложение, которое не является ни тавтологией, ни противоречием, называется случайностью.

Пример:

1.это тавтология.
2. противоречие.
3. это непредвиденное обстоятельство.

Определение логической эквивалентности
Формально
Два предложения, которые считаются логически эквивалентными, если Тавтология . Обозначения используются для обозначения этого и являются логически эквивалентными.
Один из способов доказать, что два предложения логически эквивалентны, — использовать таблицу истинности. Таблица истинности должна быть идентична для всех комбинаций, чтобы данные предложения были эквивалентны.Но этот метод не всегда осуществим, поскольку предложения могут быть все более сложными как по количеству используемых пропозициональных переменных, так и по размеру выражения.
В этом случае должен быть лучший способ доказать, что два данных предложения логически эквивалентны. Этот лучший способ — построить математическое доказательство, которое использует уже установленные логические эквивалентности для построения дополнительных более полезных логических эквивалентностей.
Некоторые основные установленные логические эквивалентности приведены в таблице ниже:

В приведенных выше логических эквивалентностях используются только конъюнкция, дизъюнкция и отрицание.Другие логические эквивалентности с использованием условных и двухусловных операторов:

Пример:
Покажите это.

Учитывая LHS,

Другой пример,
Покажите это.

Учитывая LHS,

Приведенные выше примеры можно легко решить с помощью таблицы истинности. Но это можно сделать только для предложения, имеющего небольшое количество пропозициональных переменных. Когда количество переменных растет, метод таблицы истинности становится непрактичным.
Для предложения, содержащего 20 переменных, строки должны быть оценены в таблице истинности. Это может быть легко сделать с помощью компьютера, но даже компьютер не сможет вычислить таблицу истинности предложения, имеющего 1000 переменных.

GATE CS Corner Questions

Выполнение следующих вопросов поможет вам проверить свои знания. Все вопросы задавались в GATE в предыдущие годы или в пробных тестах GATE. Настоятельно рекомендуется попрактиковаться в них.
1.GATE CS 2008, Вопрос 33
2. GATE CS 2014 Набор-2, Вопрос 63
3. GATE CS 2006, Вопрос 27
4. GATE CS 2015 Набор-3, Вопрос 65

Ссылки,
Логическая эквивалентность — Википедия
Дискретный Математика и ее приложения, Кеннет Х. Розен

Эту статью предоставил Чираг Манвани . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по почте @ geeksforgeeks.орг. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или если вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

Вниманию читателя! Не прекращайте учиться сейчас. Практикуйте экзамен GATE задолго до самого экзамена с помощью предметных и общих викторин, доступных в курсе серии тестов GATE .

Изучите все концепции GATE CS с бесплатными живыми классами на нашем канале YouTube.

L04: Комбинированная логика

L04: Комбинационная логика

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

Функциональная спецификация является частью статической дисциплины, которую мы использовать для построения комбинационной логической абстракции схемы. Один из подходов — использовать естественный язык для описания работа устройства. У этого подхода есть свои плюсы и минусы.В его пользу, естественный язык может передавать сложные концепции в удивительно компактная форма, и это обозначение, которое большинство из нас умеют читать и понимать. Но, если только слова не очень тщательно продуманный, слова могут вносить двусмысленность с множественными толкованиями или неполнотой, поскольку не всегда очевидно, все ли возможности разобрались.

Есть хорошие альтернативы, устраняющие недостатки упомянутое выше. Таблицы истинности представляют собой простую табличную представление, которое определяет значения выходов для каждого возможная комбинация цифровых входов.3 = 8 $ комбинаций трех входных значений, поэтому имеется 8 строк в таблице истинности. Это просто систематически перечислять 8 комбинаций, что упрощает чтобы гарантировать, что никакая комбинация не пропущена при построении Технические характеристики. А так как выходные значения указаны явно, нет места неверному истолкованию желаемый функционал!

Таблицы истинности — отличный выбор для устройств с небольшим количество входов и выходов. К сожалению, на самом деле это не так практично, когда у устройств много входов.{64} $ строк. Хм, не знаю как практично то есть! Если мы ввели правильное выходное значение для строки один раз в секунду, потребуется 584 миллиарда лет, чтобы заполнить стол!

Другая альтернативная спецификация — использовать булевы уравнения. чтобы описать, как вычислить выходные значения из входных значения с использованием булевой алгебры. Мы используем операции логические операции И, ИЛИ и XOR, каждая из которых требует двух Логические операнды и NOT, который принимает единственный логический операнд.Используя таблицы истинности, описывающие эти логические операции, легко вычислить выходное значение из конкретная комбинация входных значений с использованием последовательности операции, изложенные в уравнении.

Позвольте мне сказать несколько слов об обозначениях, используемых для Boolean уравнения. Входные значения представлены именем вход, в этом примере один из A, B или C. Цифровой входное значение 0 эквивалентно логическому значению FALSE и значение цифрового входа 1 эквивалентно логическому значению ПРАВДА.

Логическая операция НЕ обозначается горизонтальной линией. нарисованный над логическим выражением. В этом примере первый символ, следующий за знаком равенства, — это буква C с линией над ним, указывая, что значение C должно быть инвертировано перед он используется при вычислении остальной части выражения.

Логическая операция И представлена умножением операция с использованием стандартных математических обозначений. Иногда мы будем использовать явный оператор умножения — обычно записывается как точка между двумя логическими выражениями — как показано в первом члене примера уравнения.Иногда оператор И является неявным, как показано в оставшихся трех условия примера уравнения.

Логическая операция ИЛИ представлена сложением операция, всегда отображается как знак «+».

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

Таблицы истинности и булевы уравнения взаимозаменяемы. Если мы есть логическое уравнение для каждого выхода, мы можем заполнить столбцы вывода для строки таблицы истинности путем оценки Булевы уравнения, использующие конкретную комбинацию входных данных значения для этой строки.Например, чтобы определить значение Y в первой строке таблицы истинности мы заменим Логическое значение FALSE для символов A, B и C в уравнении а затем используйте булеву алгебру для вычисления результата.

Мы можем пойти и другим путем. Мы всегда можем преобразовать правду таблицу в особую форму логического уравнения, называемую сумма произведений. Посмотрим, как …

Начните с просмотра таблицы истинности и ответа на вопрос. «Когда Y имеет значение 1?» Или на языке булевой алгебры: «Когда Y ИСТИНА?» Ну, Y ИСТИНА, когда входные данные соответствуют строке 2 таблицы истинности, ИЛИ в ряд 4, ИЛИ в ряды 7 ИЛИ 8.Всего 4 комбинации входов, для которых Y — ИСТИНА. Соответствующие Таким образом, логическое уравнение представляет собой ИЛИ для четырех членов, где каждый член является логическим выражением, которое принимает значение ИСТИНА для определенного комбинация входов.

Строка 2 таблицы истинности соответствует C = 0, B = 0 и A = 1. В соответствующее логическое выражение: $ \ overline {C} \ cdot \ overline {B} \ cdot A $, выражение, которое оценивается как ИСТИНА тогда и только тогда, когда C равно 0, B равно 0, а A — 1.

Логическое выражение, соответствующее строке 4, — $ \ overline {C} \ cdot B \ cdot A $.И так далее для строк 7 и 8.

Этот подход всегда дает нам выражение в виде сумма произведений. «Сумма» относится к операциям ИЛИ и «Продукты» относятся к группам операций И. В этом Например, у нас есть сумма четырех терминов продукта.

Нашим следующим шагом будет использование логического выражения в качестве рецепта для построение схемной реализации с использованием комбинационной логики ворота.

Как разработчики схем, мы будем работать с библиотекой комбинационные логические вентили, которые либо даются нам производитель интегральных схем, или которые мы разработали мы в качестве ворот CMOS, используя переключатели NFET и PFET.

Одним из самых простых вентилей является инвертор, имеющий схематический символ показан здесь. Маленький кружок на выходе провод указывает на инверсию, обычное соглашение, используемое в схемы. Из его таблицы истинности видно, что инвертор реализует логическую функцию НЕ.

Элемент И выводит 1 тогда и только тогда, когда на входе A 1 и вход B равен 1, отсюда и название AND. Библиотека будет обычно включают логические элементы И с 3 входами, 4 входами и т. д., который производят 1 выход тогда и только тогда, когда все их входы 1.

Логический элемент ИЛИ выводит 1, если вход A равен 1 * или *, если вход B равно 1, отсюда и название OR. Опять же, библиотека обычно включить логические элементы ИЛИ с 3 входами, 4 входами и т. д., которые производят 1 выход, когда хотя бы один из их входов 1.

Это стандартные условные обозначения для вентилей И и ИЛИ. Обратите внимание, что символ И находится прямо на стороне ввода, в то время как символ ИЛИ изогнут. Немного попрактиковавшись, вы легко запомнить, какие условные обозначения какие.

Теперь давайте используем эти строительные блоки для построения схемы. который реализует логическое уравнение суммы произведений.

Структура схемы в точности повторяет структуру булево уравнение. Мы используем инверторы для выполнения необходимых Логические операции НЕ. В уравнении суммы произведений инверторы работают на определенных входных значениях, в этом случае A, B и C. Чтобы схема была удобна для чтения, мы использовали отдельный инвертор для каждой из четырех операций НЕ в Логическое уравнение, но в реальной жизни мы можем инвертировать вход C один раз, чтобы произвести сигнал NOT-C, затем использовать этот сигнал всякий раз, когда Необходимо значение NOT-C.

Каждый из четырех терминов продукта построен с использованием 3-входного И ворота. И термины продукта объединены ИЛИ с использованием 4-входного ИЛИ ворота. Последняя схема имеет слой инверторов, слой И ворота и последние ворота ИЛИ. В следующем разделе мы поговорить о том, как построить логические элементы И или ИЛИ с множеством входных данных из компоненты библиотеки с меньшим количеством входов.

Задержка распространения для схемы суммы произведений выглядит довольно короткий: самый длинный путь от входов к выходам включает инвертор, логический элемент И и логический элемент ИЛИ.Мы действительно можем реализовать любое логическое уравнение в схеме с $ t _ {\ textrm {PD}} $ из трех задержек гейта?

На самом деле нет, так как построение И и ИЛИ со многими входами будет требуются дополнительные слои компонентов, которые увеличивают Задержка распространения. Мы узнаем об этом в следующем раздел.

Хорошая новость в том, что теперь у нас есть простые методы для преобразования таблицы истинности в соответствующую логическое уравнение суммы произведений, и для построения схемы который реализует это уравнение.

В нашем списке дел из предыдущего раздела мы выясняем, как построить логические элементы И и ИЛИ с множеством входов. Это будет необходимо при создании схемных реализаций с использованием уравнение суммы продуктов в качестве нашего шаблона. Предположим в нашей библиотеке ворот есть только ворота с 2 входами, и мы знаем, как построить более широкие ворота, использующие 2-входные ворота в качестве строительных блоков. Мы будем работать над созданием вентилей с 3 и 4 входами, но подход, который мы используем, можно обобщить для создания логических элементов И и ИЛИ любой желаемой ширины.

Подход, показанный здесь, основан на ассоциативном свойстве оператор И. Это означает, что мы можем выполнить N-образное И с помощью выполнение парных операций И в любом удобном порядке. Операции OR и XOR операции также ассоциативны, поэтому будет работать тот же подход для разработки широких схем OR и XOR из соответствующих 2-х входной вентиль. Просто замените логические элементы ИЛИ с двумя входами или ИЛИ с двумя входами. ворота для 2-входных элементов И, показанных ниже, и вы хорошо пойти!

Давайте начнем с разработки схемы, которая вычисляет AND трех входов A, B и C.В показанной здесь схеме мы сначала вычислить (A AND B), затем AND, чтобы получить результат C.

Используя ту же стратегию, мы можем построить логический элемент И с 4 входами из три 2-входных логических элемента И. По сути, мы создаем цепочка логических элементов И, реализующих N-образное И с использованием N-1 2-входные И ворота.

Мы также можем связать четыре входа по-другому: вычисление (A AND B) параллельно с (C AND D), затем объединение эти два результата с использованием третьего логического элемента И. Используя этот подход, мы строим дерево ворот И.

Какой подход лучше: цепи или деревья? Сначала мы должны решить, что мы подразумеваем под словом «лучший». При проектировании цепей, нас интересует стоимость, которая зависит от количество компонентов и производительность, которую мы характеризуем задержка распространения цепи.

Обе стратегии требуют одинакового количества компонентов, так как общее количество парных операторов И в обоих случаях одинаково. Так это ничья при рассмотрении затрат. Теперь рассмотрим Задержка распространения.

Цепная схема в середине имеет $ t _ {\ textrm {PD}} $, равное 3. задержки ворот, и мы видим, что $ t _ {\ textrm {PD}} $ для Цепочка N-входов будет иметь задержки затвора N-1. Задержка распространения цепочки линейно растут с количеством входов.

Схема дерева внизу имеет $ t _ {\ textrm {PD}} $, равное 2 ворота, меньшие, чем цепь. Задержка распространения деревьев логарифмически растет с количеством входов. Конкретно, задержка распространения древовидных схем, построенных с использованием вентилей с 2 входами растет как log2 (N).Когда N велико, древовидные схемы могут иметь значительно лучшая задержка распространения, чем в цепных схемах.

Задержка распространения — это верхняя граница задержки в наихудшем случае. от входов к выходам и является хорошим показателем производительности предполагая, что все входные данные поступают одновременно. Но в целом цепи, A, B, C и D могут прибыть в разное время в зависимости от $ t _ {\ textrm {PD}} $ схемы, генерирующей каждый. Предположим, что вход D поступает значительно позже другого. входы.Если бы мы использовали древовидную схему для вычисления И всех четыре входа, дополнительная задержка при вычислении Z составляет два элемента задержки после прибытия D. Однако, если мы воспользуемся цепочкой цепи, дополнительная задержка в вычислении Z может быть столь же малой как одна задержка ворот.

Мораль этой истории: трудно понять, что реализация подсхемы, как показано здесь 4-входное И, даст наименьшее общее значение $ t _ {\ textrm {PD}} $, если мы не знаем $ t _ {\ textrm {PD}} $ схем, которые вычисляют значения для входных сигналов.

При разработке схем КМОП отдельные вентили естественно инвертирование, поэтому вместо использования логических элементов AND и OR, в лучшем случае производительность, которую мы хотим использовать, показанные вентили NAND и NOR здесь. Логические элементы NAND и NOR могут быть реализованы как одна CMOS вентиль, включающий одну схему подтягивания и одну схему подтягивания. А ТАКЖЕ и логическим элементам ИЛИ требуются два элемента КМОП в их реализация, например , логический элемент NAND, за которым следует ИНВЕРТОР. Мы поговорим о том, как построить сумму произведений. схемы с использованием NAND и NOR в следующем разделе.

Обратите внимание, что операции NAND и NOR не ассоциативны: И-НЕ (A, B, C) не равно NAND (NAND (A, B), C). Итак, мы не может построить логический элемент NAND с множеством входов, построив дерево NAND с 2 входами. Мы поговорим об этом в следующем раздел тоже!

Мы упоминали операцию «исключающее ИЛИ», иногда вызывал XOR несколько раз. Эта логическая функция очень полезна при построении схем для арифметических вычислений или вычислений на четность. Как вы увидите в лабораторной работе 2, реализация логического элемента XOR с двумя входами потребуется гораздо больше NFET и PFET, чем требуется для 2-входного ИЛИ ИЛИ НЕ.

Мы знаем, что можем придумать выражение суммы произведений для любую таблицу истинности и, следовательно, построить реализацию схемы, используя ИНВЕРТОРЫ, И ворота, ИЛИ ворота. Оказывается, мы можем построить схемы с той же функциональностью, использующие только 2-INPUT NAND ворота — мы говорим, что 2-INPUT NAND — это универсальные ворота.

Здесь мы показываем, как реализовать построение суммы произведений блоки, использующие только 2-входные вентили NAND. Через минуту мы показать более прямую реализацию для суммы продуктов с использованием только NAND, но эти маленькие схемы являются доказательством правильности концепции. показывая, что существуют эквивалентные схемы только для NAND.

2-INPUT NOR ворота также универсальны, как показывают эти маленькие схемы.

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

Сейчас самое время взглянуть на документацию к библиотеке логических вентилей, которую мы будем использовать для наши проекты — ищите раздаточный материал Стандартная библиотека ячеек . Информация на этом слайде взята оттуда.

В библиотеке есть оба инвертирующих затвора (например, инверторы, NAND и NOR) и неинвертирующие вентили (такие как буферы, AND и ИЛИ).Зачем включать оба типа ворот? Не сделал мы просто узнаем, что можем построить любую схему, используя только NAND или НИ?

Хорошие вопросы! Мы получим некоторое представление об ответах, если мы посмотрите на эти три реализации для 4-входного И функция.

Верхняя схема представляет собой прямую реализацию с использованием 4-входного И ворота доступны в библиотеке. $ T _ {\ textrm {PD}} $ из строб составляет 160 пикосекунд, а его размер составляет 20 квадратных микрон. Не беспокойтесь о фактических цифрах, что на этом слайде важно то, как сравниваются числа между конструкции.

Средняя схема выполняет ту же функцию, на этот раз используя вентиль NAND с 4 входами, подключенный к инвертору, чтобы произвести И функциональность, которую мы хотим. $ T _ {\ textrm {PD}} $ этого цепь составляет 90 пикосекунд, что значительно быстрее, чем одиночная ворота выше. Компромисс в том, что размер несколько больше.

Как такое может быть? Тем более что мы знаем вентиль И реализация — пара NAND / INVERTER, показанная посередине схема. Ответ в том, что создатели библиотеки решили сделать неинвертирующие ворота маленькими, но медленными, используя полевые МОП-транзисторы с гораздо меньшей шириной, чем используется в инвертирующих логических вентилях, которые были разработаны, чтобы быть быстрыми.

Зачем нам вообще использовать медленные ворота? Помните, что задержка распространения цепи задается самым длинным путем в сроки задержки от входов к выходам. В сложной схеме, есть много путей ввода / вывода, но это только компоненты на самом длинном пути, которые должны быть быстрыми, чтобы достичь наилучшего возможного общего $ t _ {\ textrm {PD}} $. В компоненты на других, более коротких путях, потенциально могут быть немного помедленнее. И компоненты на коротких путях ввода / вывода могут быть действительно очень медленно.Итак, для частей схемы, которые не чувствительны к скорости, это хороший компромисс для использования более медленные, но меньшие ворота. Общая производительность не пострадали, но общий размер улучшился.

Так что для повышения производительности мы будем проектировать с инвертированием ворота, а для наименьшего размера мы спроектируем неинвертирующие ворота. Создатели библиотеки ворот спроектировали доступные ворота с учетом этого компромисса.

Инвертирующие вентили с 4 входами также разработаны с учетом этого компромисс в виду.Для максимальной производительности мы хотим используйте древовидную схему 2-входных вентилей, как показано в нижнем схема. Эта реализация сокращает время на 10 пикосекунд. $ t _ {\ textrm {PD}} $, но обойдется нам немного дороже по размеру.

Присмотритесь к нижнему контуру. Эта схема дерева использует два логических элемента И-НЕ, выходы которых объединены с вентилем ИЛИ-НЕ. Действительно ли это вычисляет AND для A, B, C и D? Ага, как ты можно проверить, построив таблицу истинности для этого комбинационного система, использующая таблицы истинности для NAND и NOR.

Эта схема является хорошим примером применения особая логическая идентичность, известная как закон Деморгана. Есть две формы закона Деморгана, обе из которых показано здесь. Верхняя форма — это та, которая нас интересует для анализа нижнего контура. Это говорит нам, что НИ А with B эквивалентно AND для (NOT A) с (NOT B). Итак Логический элемент ИЛИ-НЕ с 2 входами можно рассматривать как логический элемент И с 2 входами с инвертирующие входы. Как это помогает? Теперь мы видим, что нижний контур на самом деле является деревом логических элементов И, где инвертирующие выходы первого слоя совпадают с инвертирующими входы второго слоя.

В первый раз это немного сбивает с толку, но с практикой вам будет удобно использовать Деморган закон при построении деревьев или цепочек инвертирующей логики.

Используя закон Деморгана, мы можем ответить на вопрос, как создавать NAND и NOR с большим количеством входов. Наши ворота Библиотека включает инвертирующие вентили до 4 входов. Зачем останавливаться там? Ну, в цепочке выпадающего списка 4-входного логического элемента И-НЕ 4 NFET включены последовательно, а сопротивление проводящих каналов составляет начинаю складывать.Мы могли бы сделать NFET шире, чтобы компенсировать, но тогда ворота становятся намного больше и шире NFET-транзисторы создают более высокую емкостную нагрузку на входные сигналы. В количество возможных компромиссов между размером и скоростью растет быстро с количеством входов, поэтому обычно разработчику библиотеки лучше всего остановиться на воротах с 4 входами и позволить схемотехник берет это оттуда.

К счастью, закон Деморгана показывает нам, как строить деревья из чередование NAND и NOR для построения инвертирующей логики с большим количество входов.Здесь мы видим схему для 8-входной NAND и вентиль ИЛИ-НЕ с 8 входами.

Подумайте о среднем уровне вентилей ИЛИ-НЕ в левой цепи как И вентили с инвертирующими входами, и тогда легко увидеть что схема представляет собой дерево И с инвертирующим выходом.

Точно так же подумайте о среднем слое вентилей NAND справа. схему как логические элементы ИЛИ с инвертирующими входами и видим, что есть дерево логических элементов ИЛИ с инвертирующим выходом.

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

Давайте визуализируем закон Деморгана в действии наверху схема. Логический элемент И-НЕ с Y на выходе может быть преобразован по закону Деморгана в логический элемент ИЛИ с инвертирующими входами. Итак, мы можем перерисовать схему в левом верхнем углу как схему показано вверху справа. Теперь обратите внимание, что инвертирующие выходы первого слоя отменяются инвертирующими входами второй слой, шаг, который мы можем показать визуально, удалив соответствующие инверсии.И, вуаля, мы видим схему NAND / NAND в форме суммы продуктов: слой инверторов, слой AND ворота и ворота ИЛИ, чтобы объединить термины продукта.

Мы можем использовать аналогичную визуализацию для преобразования выходного вентиля нижнего контура, давая нам схему внизу верно. Сопоставьте пузыри, и мы увидим, что у нас то же самое логическая функция, как указано выше.

Глядя на схему NOR / NOR в левом нижнем углу, мы видим ее имеет 4 инвертора, тогда как схема NAND / NAND имеет только один.Зачем нам вообще использовать реализацию NOR / NOR? Это нужно сделать с загрузкой на входах. В верхней цепи вход A подключается в общей сложности к четырем переключателям MOSFET. В нижней цепи, он подключается только к двум переключателям MOSFET в инвертор. Итак, нижняя схема накладывает половину емкостной нагрузка на сигнал A. Это может быть значительным, если сигнал A подключен ко многим таким цепям.

Итог: когда вам нужно поститься реализация схемы И / ИЛИ для суммы произведений выражение, попробуйте использовать реализацию NAND / NAND.Это будет будет заметно быстрее, чем при использовании И / ИЛИ.

В предыдущих разделах было показано, как построить схему, которая вычисляет заданное выражение суммы произведений. Интересный вопрос, который нужно задать: можем ли мы реализовать ту же функциональность используя меньшее количество ворот или меньшие ворота? Другими словами, есть эквивалентное логическое выражение, которое требует меньшего количества операций? Булева алгебра имеет много тождеств, которые можно использовать для преобразовать выражение в эквивалент и, надеюсь, меньше, выражение.

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

Вот уравнение из начала этой главы, включает 4 товарных термина. Мы будем использовать вариант идентификация редукции, включающая логическое выражение альфа и единственная переменная A. Если посмотреть на термины продукта, средние две предлагаем возможность применить тождество сокращения, если мы позволим альфа — выражение (C AND B).Итак, мы упрощаем середину два термина продукта должны быть только альфа, , то есть , (C И B), исключив переменную A из этой части выражения.

Рассматривая теперь три продукта, мы видим, что первый и последние термины также могут быть сокращены, на этот раз позволяя альфе быть выражение (НЕ C и A). Вау, это эквивалентное уравнение значительно меньше! Считая инверсии и попарные операции, исходное уравнение имеет 14 операций, а упрощенное уравнение имеет 4 операции.Упрощенная схема была бы намного дешевле в сборке и имеет меньший размер $ t _ {\ textrm {PD}} $ в торговаться!

Выполнение такого рода логического упрощения вручную утомительно. и подвержены ошибкам. Именно такую задачу могла бы выполнить компьютерная программа. помощь с. Такие программы широко используются, но вычисление необходимо найти наименьшую возможную форму выражения растет быстрее, чем экспоненциально, поскольку количество входов увеличивается. Поэтому для более крупных уравнений программы используют различные эвристика, чтобы выбрать, какие упрощения применить.В результаты неплохие, но не обязательно оптимальные. Но это конечно лучше делать упрощение вручную!

Еще один способ подумать об упрощении — поискать таблица истинности для ситуаций безразличия. Например, посмотрите на первую и третью строки исходной таблицы истинности на слева. В обоих случаях A равно 0, C равно 0, а выход Y равен 0. Единственная разница — это значение B, которое, как мы можем определить, равно не имеет значения, когда и A, и C равны 0. Это дает нам первую строку таблицы истинности справа, где мы используем X, чтобы указать, что значение B не имеет значения, когда A и C оба равны 0.От сравнивая строки с одинаковым значением Y, мы можем найти другие безразличные ситуации.

В таблице истинности с безразличием всего три строки. где результат равен 1. И, по сути, последняя строка является избыточной. в том смысле, что совпадающие входные комбинации (011 и 111) закрыты вторым и четвертым рядами.

Термины продукта, полученные из строк второй и четвертой, точно соответствуют условия продукта, которые мы нашли, применив сокращение личность.

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

Здесь показана упрощенная схема. Посмотрим, как он работает, когда A равно 1, B равно 1, а C выполняет переход от 1 до 0. Перед переходом C равно 1, и мы можем видеть из аннотированные значения узла, что это нижний логический элемент И что приводит к выходу Y равным 1.

Когда C переходит в 0, нижний логический элемент AND выключается и верхний вентиль И включается, и, в конце концов, выход Y становится 1 очередной раз. Но включение верха И задерживается из-за $ t _ {\ textrm {PD}} $ инвертора, поэтому кратко период времени, когда ни один логический элемент И не включен, а выход на мгновение становится 0.Эта короткая отметка в значении Y называется сбой, и это может привести к краткосрочным изменениям на многих значения узла по мере его распространения через другие части схемы. Все эти изменения потребляют электроэнергию, поэтому было бы хорошо избежать вот такие глюки, если можно.

Если мы включим в нашу реализацию третий термин продукта BA, схема по-прежнему вычисляет тот же долгосрочный ответ, что и раньше. Но теперь, когда A и B оба высоки, выход Y будет 1 независимо от значения входа C.Итак, 1 к 0 переход на входе C не вызывает сбоев на входе Y выход. Если вы вспомните последний раздел предыдущей главы, фраза, которую мы использовали для описания таких цепей, — lenient .

При попытке минимизировать выражение суммы произведений с помощью сокращение идентичности, наша цель — найти два термина продукта, которые можно записать как один меньший член продукта, исключив безразличная переменная. Это легко сделать, когда два термины продукта взяты из соседних строк в таблице истинности.Для Например, посмотрите на две нижние строки в этой таблице истинности. С выход Y равен 1 в обоих случаях, обе строки будут представлены в выражении суммы произведений для этой функции. Его легко заметить переменную безразличия: когда C и B оба 1, значение A не требуется для определения значения of Y. Таким образом, последние две строки таблицы истинности могут быть представлен одним термином продукта (B AND C).

Найти эти возможности было бы легче, если бы мы реорганизовали таблица истинности, чтобы соответствующие условия продукта были на соседние ряды.Вот что мы сделали в Карта Карно, сокращенно K-карта, показана справа. K-карта организует таблицу истинности как двумерную таблицу с ее строки и столбцы, помеченные возможными значениями для входы. На этой K-карте первая строка содержит записи о том, когда C равно 0, а вторая строка содержит записи, когда C равно 1. Точно так же первый столбец содержит записи для случаев, когда A равно 0 и B равно 0. И так далее. Записи в K-карте — это в точности так же, как записи в таблице истинности, они просто отформатировал иначе.

Обратите внимание, что столбцы перечислены в особой последовательности. это отличается от обычной двоичной последовательности счета. В этой последовательности, называемой кодом Грея, соседние метки отличаются ровно одна из их частей. Другими словами, для любых двух соседних столбцы, либо значение метки A изменилось, либо значение метки B.

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

Нотацию K-карты легко расширить до таблиц истинности. для функций с 4 входами, как показано здесь. Мы использовали Последовательность кода Грея как для строк, так и для столбцов. В виде раньше крайний левый и крайний правый столбцы смежны, как и верхний и нижний ряды.Опять же, когда мы переходим к соседнему столбец или соседняя строка, только одна из четырех меток ввода изменится.

Чтобы построить K-карту для функций от 6 переменных, нам понадобится Матрица значений 4х4х4. Это сложно нарисовать в 2D страницы, и было бы сложно определить, какие ячейки в 3D матрицы были смежными. Для более чем 6 переменных нам понадобится дополнительные габариты. Что-то, с чем мы можем справиться с компьютерами, но трудно тем из нас, кто живет только в трехмерном космос!

На практике K-карты хорошо работают до 4 переменных, и мы будем придерживаться этого.Но имейте в виду, что вы можете обобщить технику K-карты на более высокие измерения.

Так зачем говорить о K-картах? Поскольку паттерны соседней K-карты записи, содержащие единицы, откроют возможности для используя более простые термины продукта в нашей сумме продуктов выражение.

Давайте представим понятие импликанта, причудливого имени. для прямоугольной области K-карты, где все элементы 1’s. Помните, что если введена 1, нам понадобится выражение суммы продуктов, которое нужно оценить как ИСТИНА для этого конкретная комбинация входных значений.

Мы требуем, чтобы ширина и длина импликанты были из 2, , то есть , область должна иметь 1, 2 или 4 строки и 1, 2 или 4 столбца.

Это нормально, когда импликанты накладываются друг на друга. Мы говорим, что импликант — это первичный импликант , если он не полностью содержится в любом другом импликанте. Каждый термин продукта в нашем окончательное минимизированное выражение суммы произведений будет связано с некоторая простая импликанта в K-отображении.

Давайте посмотрим, как эти правила работают на практике, используя эти два примера K-карт.Когда мы определяем основные импликанты, обведем их красным. Начиная с K-карты на слева первая импликанта содержит одноэлементную 1-ячейку не примыкает ни к какой другой ячейке, содержащей 1’s.

Второй простой импликант — это пара смежных единиц в верхний правый угол K-карты. Этот импликант имеет одна строка и два столбца, отвечающие нашим ограничениям на неявные размеры.

Нахождение простых импликант в правой K-карте немного сложнее.Напоминая, что левый и правый столбцы рядом, мы можем обнаружить простой импликант 2×2. Обратите внимание, что это простая импликанта содержит много меньших 1×2, 2×1 и 1×1 импликанты, но ни один из них не будет первостепенным, поскольку они полностью содержатся в импликанте 2×2.

Заманчиво нарисовать импликант 1×1 вокруг оставшихся 1, но на самом деле мы хотим найти самый большой импликант, который содержит именно эту ячейку. В данном случае это Здесь показан простой импликант 1×2.Почему мы хотим найти наибольшие возможные основные импликанты? Мы ответим на это вопрос через минуту …

Каждый импликант может быть однозначно идентифицирован термином продукта, Логическое выражение, которое принимает значение ИСТИНА для каждой ячейки содержится в импликанте и ЛОЖЬ для всех остальных ячеек. Так же, как мы сделали для строк таблицы истинности в начале этого главы, мы можем использовать метки строк и столбцов, чтобы помочь нам построить правильный термин продукта.

Первый импликант, обведенный нами в кружок, соответствует термину продукта. $ \ overline {A} \ cdot \ overline {B} \ cdot C $, выражение, которое принимает значение ИСТИНА, когда A равно 0, B равно 0 и C равно 1.

Как насчет импликанта 1×2 в верхнем правом углу? Мы не хочу включать входные переменные, которые меняются по мере того, как мы двигаться в импликанте. В этом случае два входных значения постоянными остаются C (имеющее значение 0) и A (которое имеет значение 1), поэтому соответствующий член продукта $ A \ cdot \ overline {C} $.

Вот два термина продукта для двух основных импликант в правое K-отображение. Обратите внимание, что чем больше штрих неявно, тем меньше срок продукта! В этом есть смысл: поскольку мы перемещаемся внутри большого импликанта, количество входов которые остаются постоянными по всей импликанте, меньше.Теперь мы понимаем, почему мы хотим найти наибольшее возможное простое число. импликанты: они дают нам наименьшие условия продукта!

Давайте попробуем другой пример. Помните, что мы ищем самые большие возможные основные импликанты. Хороший способ Чтобы продолжить, нужно найти некоторую не обведенную цифру 1, а затем определить самый большой импликант, который мы можем найти, который включает в себя эту клетку.

Есть импликант 2×4, покрывающий два средних ряда стола. Глядя на единицы в верхнем ряду, мы можем идентифицировать две импликанты 2×2, которые включают эти клетки.

Правый столбец покрывает импликант 4×1, оставив одинокую 1 в нижнем левом углу таблицы. Искать соседние единицы и запоминать таблицу — это циклический, мы можем найти импликант 2×2, включающий этот последний не в кружке 1.

Обратите внимание, что мы всегда ищем максимально возможное неявно, с учетом ограничения, что каждое измерение должно быть либо 1, 2 или 4. Именно эти самые важные имплициты будут оказываются главными импликантами.

Теперь, когда мы определили основные импликанты, мы готовы построить минимальную сумму продуктов выражение.

Вот два примера K-карт, где мы показали только главные импликанты должны были покрыть все единицы на карте. Это означает, например, что в карте с 4 переменными мы не включал импликант 4×1, покрывающий правую столбец. Этот импликант был главным импликантом, поскольку он не было полностью сдержано каким-либо другим импликантом, но это не нужно было прикрывать всех, кто в Таблица.

Взглянув на верхний стол, мы соберем минимальный выражение суммы продуктов путем включения условий продукта для каждый из показанных импликантов. Верхний импликант имеет продукт термин А И (не С), а нижний импликант имеет произведение термин (B И C). Готово! Почему в результате уравнение минимальное? Если было еще какое-то сокращение, это можно было бы применить, чтобы произвести еще меньший термин продукта, который будет означать, что существует более крупный главный импликант, который может иметь был обведен кружком на K-карте.

Глядя на нижнюю таблицу, мы можем собрать сумму произведений выражение посередине. Было 4 основных импликанта, так что в выражении 4 продукта.

И мы закончили. Нахождение простых импликант в K-отображении — это быстрее и менее подвержено ошибкам, чем дурачиться с Boolean алгебраические тождества.

Обратите внимание, что выражение минимальной суммы произведений не является обязательно уникальный. Если бы мы использовали другое сочетание простых чисел при создании нашего прикрытия мы бы придумали различное выражение суммы произведений.Конечно, двое выражения эквивалентны в том смысле, что они производят одинаковое значение Y для любой конкретной комбинации входных значений — в конце концов, они были построены из одной и той же таблицы истинности. И два выражения будут иметь одинаковое количество операции.

Итак, когда вам нужно найти минимальную сумму продуктов выражение для функций до 4 переменных, K-карты — это путь идти!

Мы также можем использовать K-карты, чтобы помочь нам удалить глюки из вывода сигналы.Ранее в этой главе мы видели эту схему и заметил, что когда A было 1, а B было 1, то переход от 1 к 0 на C может вызвать сбой на выходе Y, так как нижний термин продукта отключен, а термин верхнего продукта включен.

Эта конкретная ситуация обозначена желтой стрелкой на K-карта, на которой мы переходим от ячейки на нижний ряд столбца 1–1 в ячейку верхнего ряда. Легко видеть, что мы оставляем одну неявную и переезжаем в другой.Это разрыв между двумя импликанты, которые приводят к потенциальному сбоям на Y.

Оказывается, есть главный импликант, который охватывает клетки, участвующие в этом переходе, показаны здесь красным пунктиром контур. Мы не использовали его при создании оригинала реализация суммы продуктов, поскольку два других условия продукта обеспечил необходимый функционал. Но если мы включим это имплицитно в качестве третьего термина продукта в сумме продуктов, нет на выходе Y может произойти сбой.

Чтобы упростить реализацию, просто включите все простые импликанты в выражении суммы произведений. Это мост пробелы между условиями продукта, которые приводят к потенциальному выпуску глюки.

Таблица истинности, которую мы использовали в качестве примера, описывает очень полезное комбинационное устройство, называемое мультиплексором 2-к-1. Мультиплексор, или для краткости MUX, выбирает один из двух своих входов. значения в качестве выходного значения. Когда выбран вход, отмеченный S на диаграмме равно 0, значение на входе данных D0 становится значение выхода Y.K $ входных данных. Например, вот 4 к 1 мультиплексор с 4 входами данных и 2 входами выбора.

Мультиплексоры большего размера могут быть построены из дерева мультиплексоров 2 к 1, как показано на рисунке. здесь.

Чем интересны мультиплексоры? Один ответ заключается в том, что они предоставляют очень элегантный и общий способ реализации логической функции. Рассмотрим мультиплексор 8-к-1, показанный справа. 3 входа — A, B и CIN — используются как три сигнала выбора для MUX. Думайте о трех входах как о 3-битном двоичном номер.Например, когда все они равны 0, MUX будет выберите вход данных 0, и когда все они будут равны 1, MUX будет выберите ввод данных 7 и так далее.

Как упростить реализацию логической функции, показанной в таблица истинности? Что ж, подключим входы данных MUX к постоянным значениям, показанным в выходном столбце в таблица истинности. Значения на входах A, B и CIN вызовут MUX, чтобы выбрать соответствующую константу на входах данных как значение для выхода COUT.

Если позже мы изменим таблицу истинности, нам не придется перепроектировать сложную схему суммы произведений, мы просто необходимо изменить константы на входах данных. Подумайте о MUX как устройство поиска по таблице, которое можно перепрограммировать на реализовать в этом случае любое уравнение с тремя входами. Такого рода схема может использоваться для создания различных форм программируемых логика, где функциональность интегральной схемы не определено при изготовлении, но установлено во время этапа программирования, выполняемого пользователем позже время.N $ данных входы. Они полезны для N до 5 или 6, но для функции с большим количеством входов, экспоненциальный рост в цепи размер делает их непрактичными.

Неудивительно, что мультиплексоры универсальны, как показывают эти Реализации на основе MUX для построения суммы продуктов блоки. Есть предположение, что в логике молекулярного масштаба технологии, мультиплексоры могут быть естественными воротами, так что это хорошо чтобы знать, что их можно использовать для реализации любой логической функции.

Даже XOR просто реализовать с одним мультиплексором 2 к 1!

Вот окончательная стратегия реализации логики с использованием только для чтения.K $ выходных данных. Только один из выходные данные будут 1 (или ВЫСОКОЕ) в любой момент времени, что один определяется значением на выбранных входах. Jth выход будет 1, когда выбранные строки установлены в двоичном формате представление J.

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

Три входа функции (A, B и CI) подключены к выбранным строкам декодера от 3 до 8.8 выходов декодер работает горизонтально на принципиальной схеме, и каждый помечены входными значениями, для которых этот выход будет ВЫСОКАЯ. Таким образом, когда входы равны 000, выход верхнего декодера будет быть ВЫСОКИМ, а все остальные декодеры выводят НИЗКИЙ. Когда входы 001 — , то есть , когда A и B равны 0, а CI — 1 — выход второго декодера будет ВЫСОКИМ. И так далее.

Выходы декодера управляют матрицей понижающих переключателей NFET. В матрице есть один вертикальный столбец для каждого вывода истины. Таблица.Каждый переключатель соединяет определенный вертикальный столбец с заземление, переводя его в НИЗКОЕ значение, когда переключатель включен. В Схема колонки спроектирована таким образом, что, если нет переключателей установите его значение на 0, его значение будет 1. Значение на каждом вертикальных столбцов инвертируется для получения окончательного результата значения.

Итак, как нам использовать всю эту схему для реализации функции описывается таблицей истинности? Для любой конкретной комбинации входные значения, ровно один из выходов декодера будет ВЫСОКИМ, все остальные будут низкими.Думайте о выходах декодера как о указание, какая строка таблицы истинности была выбрана входные значения. Все переключатели опускания, управляемые Будет включен выход декодера HIGH, заставляя вертикальный столбец, к которому они подключены LOW.

Например, если входы 001, выход декодера помечен 001 будет ВЫСОКИМ. Это включит выпадающий список в кружке переключатель, заставляя вертикальный столбец S НИЗКОЕ. Вертикаль COUT столбец не смещен, поэтому он будет ВЫСОКИМ.После вывода инверторы, S будет 1, а COUT будет 0, желаемый выход значения.

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

Для постоянных запоминающих устройств с большим количеством входов декодеры имеют много выходы и вертикальные столбцы в матрице переключателей могут стать довольно долго и медленно. Мы можем немного изменить конфигурацию схемы, чтобы что некоторые входы управляют декодером, а другие входы используются для выбора из нескольких более коротких и быстрых вертикальных столбцы.Эта комбинация декодеров меньшего размера и выходных мультиплексоров довольно часто встречается в схемах памяти такого типа.

ПЗУ только для чтения, сокращенно ПЗУ, являются реализацией стратегия, которая игнорирует структуру конкретного логического выражение, которое будет реализовано. Размер ПЗУ и общий Макет определяется только количеством входов и выходов. Обычно матрица переключателей заполнена полностью, со всеми возможные места переключения заполнены раскрывающимся полевым транзистором. А отдельная операция физического или электрического программирования определяет какие переключатели фактически управляются линиями декодера.N $ строк и M выходных столбцов, точно соответствующих к размеру таблицы истинности.

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

Уф! Это был головокружительный тур по разным трассам, по которым мы можно использовать для реализации логических функций.Сумма произведений подход хорошо поддается реализации с инвертированием логика. Каждая схема разработана специально для реализации определенного функции и, как таковые, могут быть как быстрыми, так и небольшими. В затраты на проектирование и изготовление таких схем составляют стоит, когда вам нужна высокая производительность или вы производите миллионы устройств.

Реализации схем MUX и ROM

в основном не зависят от конкретная функция, которая должна быть реализована. Это определяется отдельным шагом программирования, который может быть завершено после изготовления устройств.Они есть особенно подходит для прототипирования, мелкосерийного производства или устройства, функциональность которых может потребоваться обновить после устройство отсутствует в поле.

Реализация логических функций с использованием только вентилей И-НЕ или ИЛИ-ИЛИ

Взять схему, описанную с использованием вентилей И и ИЛИ, и преобразовать ее в альтернативное представление с использованием только вентилей И-НЕ или ИЛИ-НЕ — отличный способ узнать, как все работает.

Взять схему, описанную с использованием вентилей И и ИЛИ, и преобразовать ее в альтернативное представление с использованием только вентилей И-НЕ или ИЛИ-ИЛИ — отличный способ узнать, как все работает.

Это будет столбец, разделенный на три части. Это основано на вопросе, который студент задал на форумах EEWeb, и он также отправил его непосредственно вашему покорному. Суть этой головоломки такова:

Студенту было представлено логическое уравнение.
Ему было приказано создать соответствующую таблицу истинности.
Ему сказали выполнить минимизацию карты Карно.
Наконец, он должен создать реализацию, используя только вентили NAND или только вентили NOR.

Итак, мы начнем с размышлений, почему этот класс проблем должен быть поставлен в первую очередь. Далее мы рассмотрим конкретную задачу этого учащегося более подробно, приведя ее к начальному решению И-ИЛИ. Затем мы собираемся рассмотреть общие концепции перевода схем на основе И-ИЛИ в их аналоги И-И-ИЛИ. Наконец, мы воспользуемся тем, что узнали, чтобы ответить на первоначальный вопрос студента. Уф!

Почему используются только вентили NAND или только вентили NOR?

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

Хотя студенты могут быть удивлены, услышав это, не обязательно, чтобы лектор был озлобленным, разочарованным человеком, единственное удовольствие в жизни которого — усложнять жизнь своих учеников. Сказав это, вспоминая свои дни, когда я был студентом, может быть лучше не исключать это как возможную мотивацию.

Внезапно я могу вспомнить следующие причины, по которым преподаватели инструктируют своих студентов выполнять эту задачу:

Взятие схемы, описанной с использованием логических элементов И и ИЛИ в формате суммы произведений или произведения сумм, и преобразование ее в альтернативное представление с использованием только логических элементов И-НЕ, только вентилей ИЛИ или смеси И-НЕ и ИЛИ-ИЛИ ворота — отличный способ убедиться, что вы понимаете, как работают различные ворота.Это также помогает убедиться, что вы понимаете такие вещи, как преобразования ДеМоргана.
Если вы проектируете печатную плату (PCB) с использованием простых логических устройств, таких как двухрядные (DIL) интегрированные интегральные схемы (IC), содержащие шесть вентилей НЕ или четыре логических элемента И, ИЛИ, ИЛИ, ИЛИ или ИЛИ с двумя входами. , может случиться так, что вам не хватает чего-то вроде логического элемента И, но у вас есть запасные ворота И-НЕ и НЕ (или, возможно, ИЛИ и три НЕ), и в этом случае ваше понимание логических ворот может спасти день.
Простейший логический элемент — НЕ. Предполагая, что мы говорим о CMOS, тогда НЕ потребуется два транзистора. Далее по лестнице сложности идут вентили И-НЕ и И-ИЛИ, каждый из которых содержит по четыре транзистора. И затем у нас есть логические элементы И и ИЛИ, каждый из которых содержит по шесть транзисторов. Все это означает, что если мы можем использовать И-И или ИЛИ вместо И или ИЛИ, то мы можем уменьшить количество транзисторов на треть.
Что касается предыдущего пункта, логический элемент И действительно формируется из элемента И-НЕ, за которым следует элемент НЕ (аналогично элемент ИЛИ состоит из элемента ИЛИ, за которым следует элемент НЕ).Помимо использования 4 + 2 = 6 транзисторов, это означает, что логический элемент И (и логический элемент ИЛИ) состоит из двух ступеней задержки. Таким образом, если мы можем заменить наши И на И-НЕ (а наши ИЛИ на ИЛИ), наша схема будет работать быстрее.
Небольшое отступление: все, что обсуждается в этой колонке, подробно описано в моей книге Bebop to the Boolean Boogie.

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

Можно было бы утверждать, что то же самое применимо в отношении пункта 1, но я бы не согласился. Я думаю, что это похоже на концепцию использования калькулятора для выполнения ваших вычислений. Если у вас есть калькулятор, вам на самом деле не нужно знать, как выполнять сложение, вычитание, умножение и деление целых, действительных чисел и чисел с плавающей запятой, но такие знания, безусловно, пригодятся, когда батарея вашего калькулятора умирает.Точно так же, хотя вам, возможно, не нужно ежедневно манипулировать логическими конструкциями, очень удобно знать, как это делать, когда в этом возникает необходимость.

Размышляя над проблемой

Итак, вот что дал мне студент. Он начал с того, что лектор представил классу следующее уравнение:

Студент также сказал мне, что он использовал это уравнение для создания следующей таблицы истинности, но у него возникли проблемы с дальнейшим продвижением с этого момента.

Что ж, мне пришлось сказать ему, что я не удивлен, что у него возникли проблемы, потому что в его уравнении шесть членов продукта, каждому из которых должна соответствовать 1 в выходном столбце его таблицы истинности, но … на самом деле — всего пять единиц связаны с выходом в его таблице истинности.

Я много размышлял об этом и думаю, что основная проблема заключается в отсутствии понимания основных принципов. Кроме того, если один ученик сбит с толку, он, вероятно, не одинок.И последнее, но не менее важное: я помню, как я чувствовал себя «сбитым с толку и сбитым с толку», когда начинал, поэтому я собираюсь потратить время, чтобы проработать это шаг за шагом (не стесняйтесь пропустить вперед, если вам станет скучно; в качестве альтернативы вы также можете попробовать обнаружить любые преднамеренные ошибки, которые я мог допустить, чтобы проверить, обращаете ли вы внимание).

Первое, что я собираюсь сделать, это пронумеровать элементы продукта в уравнении, чтобы мы могли отслеживать, где мы находимся и что делаем (если бы мы делали это по-настоящему, мы бы не потрудитесь пронумеровать термины продукта):

Следующим шагом будет создание таблицы истинности.Мы начинаем со всех входных комбинаций, представленных в виде стандартного двоичного счета, как показано в (a) ниже, затем добавляем шесть единиц, соответствующих шести элементам продукта, как показано в пунктах (b) — (g), и, наконец, заполняем любые оставшиеся выходные «слоты» с нулями, как показано в (h) ниже.

Главное отметить здесь то, что преобразовать уравнение в таблицу истинности на самом деле совсем не сложно. Сказав это, очень важно, чтобы кто бы это ни делал, ценил логику, лежащую в основе процесса.Посмотрите на уравнение еще раз — по сути, оно говорит о том, что: «Выходные данные верны (логика 1), если первый член продукта (первая функция И) верен, ИЛИ, если второй член продукта верен, ИЛИ если третий продукт срок верен и т. д.). Вот почему мы можем просто добавить единицы к выходному столбцу, соответствующему каждому из наших терминов продукта — выход будет истинным (1), если любой из этих терминов продукта верен, иначе результат будет ложным (0).

Следующим шагом будет создание карты Карно.Начнем с создания самой сетки. Поскольку у нас есть три входа, есть два способа (варианта) сделать это, как показано ниже:

Неважно, какой из этих вариантов мы выберем. Ответ будет одинаковым в обоих случаях (если нет, то у нас действительно проблемы). Я собираюсь использовать вариант №1, потому что он мне нравится. Если кто-то из студентов читает это, я предлагаю, чтобы после того, как мы закончили, вы переделали все с этого момента, используя вариант № 2 карты Карно, чтобы убедиться, что вы действительно понимаете процесс.

Глядя на карту Варианта №1, обратите внимание, где мы показываем «AB». Справа находятся четыре комбинации нулей и единиц, которые мы можем связать с входами AB: «00», «01», «11» и «10». Очень важно заметить, что эти комбинации представлены таким образом, что они образуют код Грея, что означает, что при переходе от одного значения к смежному значению изменяется только один бит. Это ключ к способу работы карты Карно.

В двоичном коде при переходе от 01 к 10 меняются два бита.Для сравнения, если мы посмотрим на соответствующий переход в коде Грея (от 01 до 11), изменится только один бит.

Кроме того, рассмотрим самую последнюю строку двоичного кода. Если бы мы «обернулись» и перешли от этой строки к первой (с 11 по 00), то — еще раз — изменились бы два бита. Однако, если мы посмотрим на соответствующие строки в коде Грея (от 10 до 00), мы увидим, что — еще раз — изменяется только один из битов.

Хорошо, теперь давайте заполним нашу Карту Карно.Мы делаем это, добавляя единицы в каждое из полей, соответствующих условиям продукта в нашем уравнении. И снова мы сделаем это шаг за шагом, как показано ниже (маленькие числа от 1 до 6 в кружках соответствуют элементам продукта в нашем исходном уравнении):

Еще один момент, на который следует обратить внимание, это то, что нам не нужна таблица истинности для заполнения карты Карно. Все, что нам нужно сделать, это пройтись по нашему уравнению и для каждого термина продукта добавить 1 в соответствующее поле карты Карно.”

Следующим этапом является использование нашей карты Карно для минимизации логики. Глядя на окончательную карту Карно (f) выше, мы сразу же видим, что можем сократить ее только до трех членов. Как обычно, давайте делать это постепенно.

Обратите внимание на две единицы, выделенные на изображении ниже. Мы знаем, что это означает, что в обоих случаях на выходе будет 1. Для каждого из этих полей A = 0 и C = 1, поэтому эти значения важны. Однако B = 0 для одного из этих ящиков и 1 для другого. Это говорит о том, что пока A = 0 и C = 1, нам все равно, равно B 0 или 1.

Теперь давайте посмотрим на вторую группу из двух единиц, выделенную на изображении ниже. Для каждого из этих полей A = 1 и C = 0, поэтому эти значения важны. Еще раз, однако, B = 0 для одного из этих ящиков и 1 для другого. Это говорит о том, что пока A = 1 и C = 0, нам все равно, равно B 0 или 1.

И последнее, но не менее важное: давайте посмотрим на группу из четырех единиц, выделенную на изображении ниже (одна из уловок с картами Карно заключается в том, что мы можем использовать одни и те же единицы как часть нескольких групп).

В этом случае для некоторых из этих ящиков A = 0, для других A = 1, что означает, что нам все равно, равно A 0 или 1. Аналогично, для некоторых из этих ящиков C = 0, для других C = 1. , что означает, что нам все равно, равно ли C 0 или 1. Фактически, единственный вход, который является постоянным для всех ящиков, — это B, который всегда равен 1.

Все это означает, что мы можем использовать результаты минимизации нашей карты Карно, чтобы написать оптимизированное уравнение суммы произведений следующим образом:

Исходя из этого, мы можем легко нарисовать соответствующую схему на уровне ворот, используя элементы НЕ, И и ИЛИ, как показано ниже:

Прежде чем вы отправите мне электронное письмо, я знаю, что мы не используем сигнал! B (я использую здесь символ ‘!’, Чтобы указать НЕ (B), потому что я не могу провести горизонтальную линию над буквой в этом тексте. ), но мы будем использовать его в недалеком будущем.Кстати, будущее ближе, чем вы думаете. Это тот момент, когда мы должны ограничить наше мышление, потому что задача, поставленная отвратительным лектором, заключалась в том, чтобы представить окончательную схему, используя только вентили NAND или только вентили NOR.

Реализация шлюзов НЕ с использованием NAND или NOR

Давайте начнем с низко висящего фрукта, которым в этом примере будут три ворот НЕ. Во-первых, давайте напомним себе, что таблицы истинности для пяти общих примитивных ворот выглядят так, как показано ниже:

Это означает, что если мы соединим (соединим) входы с логическим элементом И-НЕ вместе, в результате получится функциональность элемента НЕ.То же самое применимо, если мы привяжем входы к вентилю ИЛИ-НЕ вместе. Это означает, что следующие функционально идентичны:

Преобразования ДеМоргана на логических элементах AND, OR, NAND и NOR

Август ДеМорган (1806–1871) был современником Джорджа Буля. ДеМорган внес значительный вклад в область символической логики; прежде всего, набор правил, которые мы теперь называем преобразованиями ДеМоргана.

Чтобы выполнить преобразование ДеМоргана для логического уравнения, мы выполняем следующие шаги:

Замените все операторы И на операторы ИЛИ, и наоборот.
Инвертировать все входные переменные; также замените любые нули на единицы, и наоборот.
Инвертировать всю функцию.
Уменьшите количество кратных инверсий.

Вообще говоря, мы склонны выполнять преобразования ДеМоргана для многочленных уравнений, но мы также можем выполнять их для отдельных вентилей, что приводит нас к следующему:

Я не знаю, как вы, и не могу объяснить, почему это должно быть, но я получаю определенное удовлетворение и чувство, что в (логическом) мире все в порядке, глядя на эквиваленты ДеМоргана выше.

Представляем нашу схему с использованием только логических элементов NAND

Если честно, теперь мы заложили основу, это самая простая часть. Напомним, как выглядит схема, с которой мы играем, когда она реализована с использованием логических элементов НЕ, И и ИЛИ:

Я закодировал их разными цветами, чтобы было понятно, что мы делаем. Давайте примем решение, что мы хотим использовать только шлюзы NAND. Итак, используя все, что мы обсуждали ранее, давайте заменим наши ворота НЕ, ИЛИ и И на ворота NAND.

Как обычно, давайте рассмотрим это постепенно. Начнем с трех ворот НЕ, которые показаны розовым слева. Мы знаем, что мы можем заменить каждый из этих вентилей на вентиль NAND с 2 входами с его входами, связанными (связанными) вместе, так что здесь нет проблем.

Теперь давайте рассмотрим логический элемент ИЛИ с 3 входами, показанный зеленым цветом справа от нашей схемы. Из наших преобразований ДеМоргана мы знаем, что можем заменить это вентилем И-НЕ с 3 входами с вентилями НЕ на его входах, как показано ниже.

И, конечно же, мы можем заменить каждый из трех вентилей НЕ логическим вентилем И-НЕ с двумя входами, как показано ниже:

Итак, все, о чем нам сейчас нужно беспокоиться, это два логических элемента И, показанные синим цветом в середине нашей схемы.Конечно, наши преобразования ДеМоргана здесь не помогают, потому что эквивалентом логического элемента И является вентиль ИЛИ с вентилями НЕ на его входах, и нам не разрешается использовать вентили ИЛИ в этом упражнении.

Иногда мы склонны усложнять вещи, чем они должны быть. Все, что нам нужно сделать в этом случае, — это помнить, что логический элемент И действительно формируется из логического элемента И-НЕ, за которым следует вентиль НЕ (аналогично вентиль ИЛИ состоит из логического элемента ИЛИ, за которым следует вентиль НЕ). Это означает, что мы можем заменить наши логические элементы AND, как показано ниже:

И, конечно же, поскольку перед нами стоит задача использовать только вентили NAND, нам придется заменить вентиль NOT его эквивалентом NAND с двумя входами, как показано ниже:

Сейчас действительно готовим, как говорится, на раскаленной плите.Итак, если мы соберем все это вместе, наша реализация только для NAND будет выглядеть следующим образом:

Схема, приведенная выше, будет выполнять желаемую функцию, но мы тратим впустую ворота, потому что у нас есть два случая вентиля НЕ, за которым следует вентиль НЕ (оба, конечно, реализованы как ворота NAND), как показано красными граничными полями ниже:

Каждый раз, когда у нас есть четное число инверсий в виде функций НЕ, мы можем заменить их простым отрезком провода. Таким образом, после небольших изысков наша последняя схема будет выглядеть следующим образом:

Если бы мы сказали, что каждый вентиль NOT, NAND и NOR приравнивается к одному уровню задержки, в то время как логические элементы AND и OR равняются двум уровням задержки, тогда пути ввода-вывода в худшем случае в нашем исходном НЕ, Реализация И и ИЛИ приравнивается к 1 + 2 + 2 = 5 задержкам.Для сравнения, наша элегантная реализация только для NAND соответствует задержкам 1 + 1 + 1 = 3.

Еще раз, если кто-то из студентов читает это, просто чтобы убедиться, что вы на 100% в курсе, я предлагаю вам использовать вышеупомянутые обсуждения в качестве основы для создания реализации только NOR. А пока я приветствую любые комментарии и вопросы, а также буду признателен за любые советы и уловки по теме, которыми могут поделиться более опытные читатели.

Дополнительное чтение

Упрощение формул логики с помощью равносильных преобразований

Примеры логических выражений

Упрощение логических выражений

Законы алгебры логики. Упрощение логических выражений.

Элементы математической логики — Практическое занятие №3 — Упрощение формул логики | Методическая разработка по теме:

По теме: методические разработки, презентации и конспекты

Равносильные преобразования

Равносильные преобразования и упрощения формул

(PDF) Минимизация конъюнктивных нормальных форм булевых функций комбинаторным методом

Propositional Logic

Раздел 3.1 Логика высказываний

Расследовать!

Подраздел Таблицы истинности

Пример 3.1.1.

Пример 3.1.2.

Подраздел Логическая эквивалентность

Логическая эквивалентность.

Пример 3.1.3.

Законы Де Моргана.

Последствия — дизъюнкции.

Двойное отрицание.

Пример 3.1.4.

Отрицание следствия.

Пример 3.1.5.

Подраздел Вычеты

Расследовать!

Пример 3.1.6.

Пример 3.1.7.

Подраздел за пределами предложений

Пример 3.1.8.

Пример 3.1.9.

Упражнения Упражнения

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18,

19.

20.

Логическая эквивалентность — обзор

5.1 Ядерные и внеядерные свойства

Логические эквиваленты

Раздел 2.1 Логические эквивалентности

Определение 2.1.1.

Определение 2.1.2.

Определение 2.1.3.

Пример 2.1.4.

Пример 2.1.9.

Упражнения 2.1.1 Упражнения

1.

2.

3.

4.

5.

Подраздел 2.1.2 Сообщения форума об этом разделе

Математика | Эквивалентность высказываний — GeeksforGeeks

L04: Комбинированная логика

L04: Комбинационная логика

Реализация логических функций с использованием только вентилей И-НЕ или ИЛИ-ИЛИ

Добавить комментарий Отменить ответ