Алгебра логики формулы: Тема 2 Формулы алгебры логики — RC74 — интернет-магазин радиоуправляемых моделей

Содержание

Тема 2 Формулы алгебры логики

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

2.2 Законы алгебры логики

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

2.1 Равносильные формулы алгебры логики. Приведем определение формулы алгебры логики.

1) каждая «элементарная» булева функция – формула;

2) если некоторое выражение N есть формула, то тоже формула;

3) если некоторые выражения M и N есть формулы, то выражения , , , тоже формулы;

4) других формул, кроме построенных по п. п.1), 2), 3), нет.

Формулы алгебры логики мы будет обозначать большими N, M, … Например, следующие выражения являются формулами алгебры логики:

, .

С целью упрощения формул, условимся, что операция конъюнкции «сильнее» операции дизъюнкции, импликации и эквивалентности, т.

е. если нет скобок, то вначале выполняется операция конъюнкции.

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

Две формулы N и M называются Равносильными, если они определяют одну и ту же булеву функцию (запись N=M будет означать, что формулы N и M равносильны).

Пример 1. Формулы и равносильны, т. е. .

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


0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

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

Очевидно, что отношение равносильности формул алгебры логики является:

1. рефлексивным, т. е. N=N для любой формулы N;

2. симметричным, т. е. если N=M, то M=N для любых формул N и M;

3. транзитивным, т. е. если N=M и M=J, то N=J для любых формул N, M,J.

Таким образом, отношение равносильности является отношением эквивалентности.

Если какую-нибудь формулу N1, являющуюся частью формулы N заменить формулой N2, равносильной N1, то полученная формула окажется равносильной N. Это свойство лежит в основе преобразования формул с целью их упрощения или приведения к определенной форме.

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

2.2 Законы алгебры логики. Приведем перечень важнейших равносильностей (законов) алгебры логики. Эти равносильности выражают свойства логических операций.

1. — закон тождества;

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

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

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

5. , — законы идемпотентности;

6. , — законы коммутативности;

7. , — законы дистрибутивности;

8. , — законы ассоциативности;

9. , — законы де Моргана;

10. ,

11. ,

12. , — законы поглощения;

13. , — законы склеивания.

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


0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

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

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

Первые две равносильности легко доказываются с помощью таблиц истинности. Две последние равносильности докажем с помощью законов де Моргана и двойного отрицания:

; .

Итак, справедливы следующие утверждения:

1) импликацию и эквивалентность можно выразить через конъюнкцию, дизъюнкцию и отрицание;

2) конъюнкцию можно выразить через дизъюнкцию и отрицание;

3) дизъюнкцию можно выразить через конъюнкцию и отрицание;

4) все операции посредством равносильных выражений можно заменить двумя: конъюнкцией и отрицанием или дизъюнкцией и отрицанием.

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

Множество булевых функций, рассматриваемое вместе с операциями отрицания, конъюнкции и дизъюнкции, называют Булевой алгеброй. Законы 1-13 являются Основными законами булевой алгебры.

Обратим внимание на характер соответствий между равносильностями, объединенными в пару под номерами (5-13). В этих соответствиях проявляется так называемый закон двойственности.

Назовем формулу алгебры логики Двойственной к формуле , если =.

Будем говорить, что операция конъюнкции двойственна операции дизъюнкции и наоборот.

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

Например, формула двойственная к формуле , а формула двойственная к формуле .

Теперь сформулируем закон двойственности.

Теорема 2. Если формулы алгебры логики N и M равносильны, то и двойственные им формулы N* и M* равносильны.

Докажем данный закон. Пусть N(X1,X2,…,XN) = M(X1,X2,…,XN). Согласно определению двойственной формулы

и .

Так как N(X1,X2,…,XN) и M(X1,X2,…,XN) принимают одинаковые значения при любых значениях переменных X1,X2,…,XN, то

Отсюда следует, что

Так как формулы и равносильны соответственно формулам и , то они равносильны между собой.

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

Пример 2. Из равносильности вытекает равносильность . Из равносильности вытекает равносильность .

< Предыдущая		Следующая >

§ 3. Законы алгебры логики — ЗФТШ, МФТИ

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

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

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

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

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

Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.

Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.

`x`	`Y`	`x&y`	`bar(x&y)`	`barx`	`bary`	`barx vv bary`
`0`	`0`	`0`	`1`	`1`	`1`	`1`
`0`	`1`	`0`	`1`	`1`	`0`	`1`
`1`	`0`	`0`	`1`	`0`	`1`	`1`
`1`	`1`	`1`	`0`	`0`	`0`	`0`

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

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

Наше начальное выражение: x `vv` (x & y). Выносим `x` за скобки и получаем следующее выражение:

x &(1 `vv` y). Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x.

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

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

1) Отрицание

2) Конъюнкция

3) Дизъюнкция, строгая дизъюнкция, эквивалентность

4) Импликация

Законы и правила булевой алгебры

следующий → ← предыдущая

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

Логическое сложение

Операция сложения в булевой алгебре аналогична операции ИЛИ. В цифровых схемах операция ИЛИ используется для вычисления суммирующего члена без использования операции И. A + B, A + B’, A + B + C’ и A’ + B + + D’ — вот некоторые из примеров «суммы». Значение термина суммы истинно, когда один или несколько литералов истинны, и ложно, когда все литералы ложны.

Булево умножение

Операция умножения в булевой алгебре аналогична операции И. В цифровых схемах операция И вычисляет произведение без использования операции ИЛИ. AB, AB, ABC и ABCD — вот некоторые из примеров термина продукта. Значение термина произведения истинно, когда все литералы истинны, и ложно, когда любой из литералов ложен.

Законы булевой алгебры

Существуют следующие законы булевой алгебры:

Коммунативное право

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

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

А+В = В+А

Для двух переменных коммутативный закон умножения записывается как:

А. Б. = Б.А.

Ассоциативный закон

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

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

А + (В + С) = (А + В) + С

Для трех переменных ассоциативный закон умножения записывается как:

А(ВС) = (АВ)С

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

Распределительный закон:

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

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

А(В + С) = АВ + АС

Правила булевой алгебры

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

1.	А+0=А	7.	А.А=А
2.	А+1=1	8.	А.А’=0
3.	А.0=0	9.	А»=А
4.	А.1=А	10.	А+АВ=А
5.	А+А=А	11.	А+А’В=А+В
6.	А+А’=1	12.	(А+В)(А+С)=А+БК

Правило 1: А + 0 = А

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию ИЛИ с 0, результат будет таким же, как и входная переменная. Итак, если значение переменной равно 1, то результатом будет 1, а если значение переменной равно 0, то результатом будет 0. Схематически это правило можно определить как:

Правило 2: (А + 1) = 1

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию ИЛИ с 1, результатом всегда будет 1. Таким образом, если значение переменной равно 1 или 0, то результатом всегда будет 1. Схематически , это правило можно определить как:

Правило 3: (А.0) = 0

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию AND с 0, результатом всегда будет 0. Это правило гласит, что входная переменная, объединенная AND с 0, всегда равна 0. Схематично это правило можно определить как:

Правило 4: (А.1) = А

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию И с 1, результат всегда будет равен входной переменной. Это правило гласит, что входная переменная, объединенная по И с 1, всегда равна входной переменной. Схематически это правило можно определить как:

Правило 5: (А + А) = А

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию ИЛИ с той же переменной, результат всегда будет равен входной переменной. Это правило утверждает, что входная переменная, объединенная ИЛИ с самой собой, всегда равна входной переменной. Схематично это правило можно определить как:

Правило 6: (А + А’) = 1

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию ИЛИ с дополнением этой переменной, результат всегда будет равен 1. Это правило гласит, что переменная, объединенная ИЛИ с ее дополнением, равна 1 всегда. Схематически это правило можно определить как:

Правило 7: (А.А) = А

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию И с той же переменной, результат всегда будет равен только этой переменной. Это правило гласит, что переменная, объединенная по И с самой собой, всегда равна входной переменной. Схематично это правило можно определить как:

Правило 8: (А.А’) = 0

Допустим; у нас есть входная переменная A, значение которой равно 0 или 1. Когда мы выполняем операцию И с дополнением этой переменной, результат всегда будет равен 0. Это правило гласит, что переменная, объединенная И с ее дополнением, равна 0 всегда. Схематически это правило можно определить как:

Правило 9: А = (А’)’

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

Правило 10: (А + АВ) = А

Мы можем доказать это правило, используя правило 2, правило 4 и распределительный закон:

A + AB = A(1 + B) Факторинг (распределительный закон)
A + AB = A.1 Правило 2: (1 + B)= 1
A + AB = A Правило 4: A .1 = A

Правило 11: А + АВ = А + В

Мы можем доказать это правило, используя приведенные выше правила как:

A + AB = (A + AB)+ AB Правило 10: A = A + AB
A+AB= (AA + AB)+ AB Правило 7: A = AA
A+AB=AA +AB +AA +AB Правило 8: сложение AA = 0
A+AB= (A + A)(A + B) Разложение на множители
A+AB = 1.(A + B) Правило 6: A + A = 1
A+AB=A + B Правило 4: отбросить 1

Правило 12: (А + В)(А + С) = А + ВС

Мы можем доказать это правило, используя приведенные выше правила как:

(A + B)(A + C)= AA + AC + AB + BC Закон распределения
(A + B)(A + C)= A + AC + AB + BC B)(A + C)= A( 1 + C)+ AB + BC Правило 2: 1 + C = 1
(A + B)(A + C)= A. 1 + AB + BC Факторинг (дистрибутивное право)
(A + B)(A + C)= A(1 + B)+ BC Правило 2: 1 + B = 1
(A + B)(A + C)= A.1 + BC Правило 4: A .1 = A
(A + B)(A + C)= A + BC

Следующая темаЛогические вентили

← предыдущая следующий →

Булева алгебра

Введение

Булева алгебра — это тип алгебры, который используется при разработке (цифровых) логических схем,
. компьютерные программы, такие как поисковые системы и вообще в аналитических рассуждениях.
Это арифметическая интерпретация логики предложений, которая также похожа на теорию множеств.
Булева алгебра была разработана британским математиком Джорджем Булем (1815–1864).

Щелкните [ ЗДЕСЬ ] для Logic10 , программы, которая обрабатывает формулы булевой алгебры.

Переменные и операторы

Логическая переменная может иметь значение «истина» или «ложь».
Для целей арифметических операций «истина» представлена «1», а ложь представлена «0».
В этой статье логическая переменная обозначается одним символом, например A, B или C.
Переменная обозначает предложение, такое как « пусковой переключатель нажат », « температура в пределах диапазона »,
« значение счетчика = 6 «, « Джону 10 лет » ….и т.д.

Обратите внимание, что высказывание либо истинно(1), либо ложно(0).
На улице светит солнце или нет. Выключатель или дверь открыты или закрыты.

Булева алгебра знает 3 основные операции: И , ИЛИ и НЕ

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

Оператор для И «. » (точка)

A	B	A.B
0	0	0
1	0	0
0	1	0
1 9006 8	1	1

A.B равно 1, если и A, и B равны 1.
В семье AND оба родителя должны согласиться удовлетворить просьбу ребенка.
Перечислены все возможные операции И между двумя переменными:

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

На картинке выше лампа горит, когда нажаты все переключатели A, B, C (истина = 1).
В диодной логике выходное напряжение высокое (1), когда все входы A, B, C имеют высокий уровень.
Диоды изолируют переменные A, B, C.

Для операций И применяется ассоциативное правило: A.(B.C) = (A.B).C
Также применяется коммуникативное правило: A.B = B.A

ИЛИ

Оператор для ИЛИ « + »

-A-	-B-	-A+B-
0	0	0
1	0	1
0	1	1
1	1	1

A+B равно 1, если любой из A и B равен 1.
В ИЛИ семье только один из родителей должен согласиться удовлетворить просьбу ребенка.

На приведенном выше рисунке свет включается при нажатии одного или нескольких переключателей A, B, C.
В диодной логике выход имеет высокий уровень (1), когда хотя бы на одном из входов высокий уровень (+12 В).

Для операций ИЛИ применяется ассоциативное правило: A+(B+C) = (A+B)+C
Также применяется коммуникативное правило: A+B = B + A

Перечислены все возможные операции ИЛИ между двумя переменными:

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

НЕ

Это отрицание ценности.
NOT — это простой оператор, помещаемый перед переменной для инвертирования ее значения.
В булевой алгебре НЕ обычно обозначается сплошной чертой над переменной, например
.

Поскольку эту верхнюю панель трудно редактировать, мы также используем / непосредственно перед переменной.
Таким образом, не A = /A = и не (A AND B) = /(A.B) =

-A-	-NOT A-
0	1
1	0

Примечание: //А = А
В электромеханике происходит обратная операция, когда нажатие на переключатель приводит к его размыканию,
препятствуя протеканию тока. (предположим, что «переключатель нажат» = «1»)
В электронике схема, выполняющая функцию НЕ, называется 9.0261 ИНВЕРТОР .

На изображении выше лампа гаснет при нажатии переключателя (/A) (1).
Инвертор (диодно-транзисторная логика) выдает 0 (0 В), когда на входе высокий уровень (12 В).

Примечание. За элементами И , ИЛИ всегда следует инвертор для усиления сигналов.
Обычной практикой являются вентили не И (НЕ-И), а не ИЛИ (НЕ).

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

Исключающее ИЛИ

Функции И и ИЛИ вместе с ИНВЕРТОРАМИ объединяются для создания более сложных схем.
Наиболее важной функцией является XOR , «исключающее ИЛИ», также называемая «логической разностью» или «полусумматор»,
потому что это ключевая функция в создании сумматоров и счетчиков.
Определение XOR: A XOR B = A./B + /A.B
Таким образом, операция XOR между A и B дает истину, если значения A и B не равны.
Примечание:
для XOR, также выполняются коммуникативные и ассоциативные законы.
Кроме того, функция XOR является собственной ИНВЕРСИЕЙ: A XOR B XOR B = A

Множественные переменные

И, ИЛИ операции могут включать более 2 переменных,
Формула A.

B.C.D даст истинное (1) только в том случае, если все A,B,C,D равны 1.
Формула A+B+C+D даст истинное (1), если хотя бы одно из A,B,C,D равно 1.
Формула A./B.C будет верна, только если A=1, B=0 (так что /B=1) и C=1.

Распределительные законы

Булева алгебра знает два дистрибутивных закона с операциями И и ИЛИ.

А.(В+С) = А.В + А.С

А + В.С = (А+В).(А+С)

Доказательство предоставляется читателю.

Несоответствие

Формула булевой алгебры называется противоречивой , если результат никогда не бывает истинным.
Простое несоответствие: А./А

Тавтология

Тавтология – это утверждение (формула), которое всегда дает истину.
Простая тавтология A + /A

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

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

Правила редукции

1. ..А + А = А

2…А + А.В = А

3…А . Б+А. /В = А

4…А + /А . B = A + B

5…A./B + A./C + BC = A + B.C

6…AB + /AC + BC = AB + /AC

Доказательства:
1. следует из определения.
2. Распределительный закон: A + A.B = A.(1 + B) = A
3. Распределительный закон: А./В + А.В = А.(/В + В) = А
4. Распределительный закон 2: A + /AB = (A + /A)(A+B) = 1. (A+B) =A + B
5. придется подождать.
6. AB + /AC + BC = AB +/AC + /ABC + ABC = AB + /AC (правило 2, объединить члены 1,4, а также 2,3)

A	B	C	A.A	A+A	A+B	A.B+A./B	A +/А.В	А./В+А./С+ B.C	A+BC
0	0	0	0	0	0	0	0	0
1	0	0	1	1	1	1	1	1	1
0	1	0	0	0	1	0	1	0	0
1	1	0	1	1	1	1	1	1	1
0	0 900 68	1	0	0	0	0	0	0	0
1	0	1	1	1	1	1	1	1	1
0	1	1	0	0	1	0	1	1	1
1	1	1 900 68	1	1	1	1	1	1	1

Примечание: правила 5.

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

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

(Правило большого пальца: разбить строку, изменить знак)
Доказательство предоставляется читателю.

Законы Де Моргана гласят, что: И для единиц является ИЛИ для нулей , а также:
ИЛИ для единиц является И для нулей

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

Еще одно доказательство правила4 с использованием законов Де Моргана:

Доказательство правила 5:

Примеры:

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

В таблице истинности перечислены все комбинации переменных, для которых формула дает «истину».
Таблица истинности имеет вид: A.

B.C + D.E.F + G.H.I + ……..
Комбинации И записываются для каждой строки, строки объединяются по ИЛИ.
Эта форма также называется «конъюнктивной нормальной формой». (CNF)
Генерация таблицы истинности формулы — это преобразование формулы в форму CNF.

Пример

В цифровом оборудовании для отображения чисел часто применяются 7-сегментные дисплеи.
Для десятичной цифры требуется 4 бита, пусть эти биты будут A (бит-0-), B (бит-1-), C (бит-2-), D (бит-3).
Мы строим таблицу истинности для случаев, когда верхний сегмент должен быть включен.

Это относится к цифрам: 0, 2, 3, 5, 6, 7, 8, 9, и таблица истинности становится

цифра	A	B	C	D
0	0 900 68	0	0	0
2	0	1	0	0
3	1	1	0	0
5	1	0	1 9006 8	0
6	0	1	1	0
7	1	1	1	0
8	0	0	0	1
9	1	0	0	1

1 в таблице означает, что переменная должна быть «1» (то есть A,B,C.

…),
0 означает, что переменная должна быть «0» (так что /A,/B,/C…..)
Первые 3 строки таблицы эквивалентны /A./B./C./D + /A.B./C./D + A.B./C./D

Таблица может быть сокращена путем применения правила A./B + А.В = А.(/В + В) = А
Для A мы читаем все равные биты, B , /B — биты с одной разницей.
Строки 1,2 для цифр 0,2 отличаются только 1 битом, поэтому их можно объединить в 0x00, где x (здесь B) — безразличный бит.
Кроме того, для цифр 5,7 бит B является единственным отличием, поэтому эти строки можно заменить на 1×10.
Строки для цифр 8,9 аналогично объединяются в x001.

Таблица истинности теперь уменьшена до

A	B	C	D
0	x	0	0
1	1	0	0
1	х	1	0
0	1	1	0
x	0	1

Строки 1,2 означают:

поэтому бит A в строке 2 может быть удален.

Теперь сравнение строк 2 и 4 приводит к исключению бита C из строки 4.
Окончательная таблица истинности становится:

А	Б	С	Г
0	x	0	0
x	1	0
1	x	1	0
0	1	x	0
x	0	0	1

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

приложений

Электромеханика

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

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

На фото выше переключатель и реле.
Назовем переключатель «А», а А = 1 означает: переключатель А нажат.
Тогда для контактов 1,2 логическая функция /A, потому что ток проходит, когда переключатель не нажат.
Контакты 3,4 выполняют функцию А, т.к. эти контакты замыкаются только при нажатии переключателя.

Реле представляет собой переключатель, который приводится в действие магнитом (катушка с железным сердечником).
Когда ток течет через катушку, переключатели нажимаются, и ток может течь через контакты:
5-6, 9-10, 13-14.
В обесточенном состоянии ток протекает через контакты 3-4, 7-8, 9-10.
Поскольку имеются все необходимые логические функции, можно построить цифровой компьютер, используя только реле.

Автобусная остановка

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

для остановок по запросу.
Кнопки представляют собой переключатели мгновенного действия. Индикатор STOP должен гореть после того, как пассажир отпустит кнопку
(не обязательно держать баттен до следующей остановки).
Таким образом, для хранения состояния STOP требуется 1-битная память.
Однако на автобусной остановке свет должен быть выключен. Условие «двери открыты» удобно для этого.
Как будет выглядеть эта схема?

A, B — переключатели над пассажирскими сиденьями. А означает «пассажир А нажимает кнопку».
Р — реле. D — дверной выключатель. D означает: двери открыты.
Переключатели и реле изображены в обесточенном (0) состоянии.
Когда пассажир нажимает кнопку, ток проходит через катушку и контакты 1,2 D (если дверь закрыта).
R возбуждается, поэтому ток течет через катушку и контакты 5,6 R (опять же, если дверь закрыта).
Когда пассажир отпускает кнопку A или B, реле остается под напряжением, пока автобус не остановится,
двери открываются, что приводит к разрыву контактов 1,2 D и обесточиванию R.

При включении R контакты 9,10 замыкаются и загорается лампа запроса СТОП.

Логическая формула для R: R = (A + B)./D + R./D = (A+B+R)./D
R, встречающийся как слева, так и справа от знака =, указывает на функцию памяти.

Электроника

В компьютерах логические функции выполняются с помощью электроники, потому что электронные переключатели являются самыми быстрыми из доступных.
Существует несколько типов логических схем, таких как DTL (диодно-транзисторная логика), TTL (транзисторно-транзисторная логика),
RTL (резисторно-транзисторная логика) и самый быстрый из всех ECL (эмиттерно-связанная логика).
Все они имеют свои определенные уровни напряжения для представления «0» или «1».
Для TTL «0» соответствует 0 ….0,8 Вольт, а «1» — любому напряжению выше 2,2 Вольт (мощность питания составляет 5 Вольт).

Ниже изображен простой логический элемент И-НЕ с входом DTL 2, где nand означает не-и: вентиль и инвертор вместе.

«1» — высокое напряжение (любое выше 8 вольт).