Логические функции двух переменных.
2
Имеется 22=16 функций (2- переменные, 2- состояния 0 или 1).
Функции эти называются КОНСТИТУАНТЫнуля и единицы.
Базовые логические операции И, ИЛИ, НЕ.
И Объединение двух высказываний в одно с помощью союза «И» называется операцией логического умножения или конъюнкцией.
Составное высказывание, образованное в результате КОНЪЮНКЦИИ, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.
| А | В | F= A & B |
На формальном языке алгебры логики операция конъюнкции обозначается значком «&» или «^ ». Например, F= A & B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
ИЛИ Объединение двух высказываний в одно с помощью союза «ИЛИ» называется операцией логического сложения или дизъюнкцией.
составное высказывание, образованное в результате ДИЗЪЮНКЦИИ, истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний.
| А | В | F= A + B |
На формальном языке алгебры логики операция дизъюнкции обозначается значком «+» или «\/ ». Например, F= A + B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
Функция «ИСКЛЮЧАЮЩЕЕ ИЛИ » 
, если 
или 
, но не одновременно. Еще ее называют «Сумма по модулю 2» или «Функция несовпадения», обозначается 
.
НЕ Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией. Инверсия делает истинное высказывание ложным и наоборот, ложное - истинным. На формальном языке отрицание обозначают чертой над аргументом.
Логические выражения. (Дать пример составления логического выражения и по нему – таблицы истинности).
 №
набора
Перем.
| ||||
| ||||
| ||||
| с |
Например, надо вычислить значение логического выражения при заданном наборе исходных переменных:
_______________
(
) 
, где
(Дать решения для каждого из наборов и на следующей лекции – контрольная работа по таким задачам – на один час.)
Кроме базовых функций, которые мы рассмотрели (И. ИЛИ и НЕ) существуют еще 13 функций от двух аргументов, которые построены на базовых. Рассмотрим две самые часто используемые: ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ (ИМПЛИКАЦИЯ) и ЛОГИЧЕСКОЕ РАВЕНСТВО
(ЭКВИВАЛЕНТНОСТЬ).
СЛЕДОВАНИЕ (ИМПЛИКАЦИЯ) обозначается стрелкой → «если А, то Б»
| А | В | F= A → B |
Составное высказывание, образованной с помощью ИМПЛИКАЦИИ (следования), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание). Докажем методом сравнения таблиц истинности, что операция ИМПЛИКАЦИИ равносильна логическому выражению НЕ А ИЛИ В, т.е. построены на базовых логических функциях:
| А | В | ⌐ А | ⌐ А \/ В |
РАВЕНСТВО (ЭКВИВАЛЕНТНОСТЬ) обозначается волнистой чертой ~ «А тогда и только тогда, когда В»
Составное высказывание, образованной с помощью эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.
| А | В | F= A ~ B |
Рассмотрим законы и теоремы алгебры логики (или Булевой алгебры):
1. 
= х
2. х + у = у + х
3. х * у = у * х
4. х + у + а = (х+у) + а = х + (у+а)
5. хуа = (ху)а = х(уа)
6. х(у+а) = ху+ха
7. х + уа = (х+у) (х+а)
8. х +х = х
9. х*х = х
10. х + 0 = х
11. х * 1 = х
12. х *0 = 0
13. х + 
=1
15. х 
=0
16. х + ху = х
17. х(х+у) + х
18. х + у = х + у
19. х( + у) = ху
20. 
= * 
* 
…
21. 
= + + …
Последние два пункта - общие случаи теоремы Де Моргана, которая звучит так: «Отрицание логической суммы равно логическому произведению отрицаний и отрицание логического произведения равно логической сумме отрицаний.»
Упрощение логических выражений с использованием теорем:
Обычно начинают с поиска следующих форм:
+ 
+ + 
,
где и либо сами логические переменные, либо произведения множеств логических переменных.
Эти структуры можно упростить:
+ = (
+ )=
+ = (1+ )=
+ =( + )+ = +(
)= 
Например: 
*у* + * * + х * * + *у * а + х*у* =
---------------- =========== ---------------- ========
сгруппируем 1-й и 4-й, 3-й и 5-й и получим:
= *у*( + )+ * * +х ( +у)= у+ +х = (у+ )+х =
= (у+ )+х = у+ +х = у+ ( +х)= у+
Вычислительные процессы в ЭВМ решаются с помощью правильно построенных логических схем, где на входе может быть несколько сигналов высокого (1) и низкого (0) уровня. Чтобы эти схемы упростить, минимизировать затраты и экономические и временные, все первоначальные логические выражения упрощаются, используя выше описанные тождества и законы Булевой алгебры.
Например; Дана схема с четырьмя аргументами – сигналами и выход S = инверсия функции F(a,b,c,d).
Запишем функцию: + В + С + ВС =
объединим 1 и 3й, 2 и 4-й:
= ( +С) + В ( + С) = + В = ( +В) = 
F(a,b,c,d)= = 
Инверсия этого выражения - 
= А +D, т.е. схема сводится к виду:
А
D
Упрощение логических выражений с использованием теорем:
Обычно начинают с поиска следующих форм:
А + АВ или А + АВ или А + В, где А и В логические переменные. Эти структуры можно упростить:
+ АВ = А( +В) = А
А + АВ = А(1 + В) = А
А + В = (А + АВ) + В = А + (АВ + В) = А + (А + 
)В = А + В
Бывает необходимость упрощения схемы в обратном порядке, то есть предлагается готовая логическая схема, которую необходимо упростить. Для этого по схеме записываются цепочки логических выражений, которые в свою очередь упрощаются уже рассмотренными методами. Значит надо уметь записывать логические выражения по предложенным схемам. НАПРИМЕР.
|
|
|
у не х
|
|
у х
_________________________ ____________ _________ ________ __ _
_ _
((х * у) + х) + ((х + у) * х) = у + х +х + х*у = у +1 + х*у = у(х+1) +1=у+1=1 = 0.
Получается при упрощении выражения, что при любых входных сигналах на выходе будет НОЛЬ, то есть эта схема может служить как генератор нуля.