1. Инверсия (унарная)
2. Конъюнкция (умножение)
3. Дизъюнкция (логическое сложение)
4. Сложение по модулю 2 (исключающеее ИЛИ)
5. Импликация (следование)
6. Эквивалентность.
Задачи
1) Для каких значений переменных функция принимает значение “ложь” ?
Решение
Логическая сумма принимает ложное значение только в одном случае, когда оба слагаемых равны 0.
Первое слагаемое: равно 0 только если A=1 и = 0, следовательно: A=1, B=1.
Второе слагаемое при A=1 может быть равно 0 только, если С=0.
Ответ: A=1, B=1, C=0.
2) Имеются две аудитории, в каждой из них должны проходить либо занятия по физике, либо по информатике.
Имеются два высказывания:
1) в одной из аудиторий проходят занятия по информатике
2) занятия по физике проходят в первой аудитории
Известно, что эти высказывания могут быть либо одновременно истинны, либо одновременно ложны.
Определить, в какой аудитории проходят занятия по информатике и в какой – по физике.
Решение
Для решения задачи необходимо перевести условие задачи на язык алгебры логики, т.е. определить переменные, соответствующие высказываниям (причем их количество должно быть минимальным) и связать эти переменные соответствующими логическими операциями.
Обозначим:
A- в первой аудитории проходят занятия по информатике,
B- во второй аудитории проходят занятия по информатике.
Поскольку в каждой аудитории обязательно должны проходить занятия либо по физике, либо по информатике, отрицаниям этих высказываний будут соответствовать:
— в первой аудитории проходят занятия по физике,
— во второй аудитории проходят занятия по физике.
Тогда первое высказывание соответствует логическому выражению:
Второе высказывание: .
Поскольку высказывания должны быть одновременно истинны либо одновременно ложно, значит функция эквивалентности этих высказываний должна быть истинна: .
Для решения этого уравнения выразим функцию эквивалентности через базовые логические функции:
Подставим вместо X и Y соответствующие логические выражения:
Упростим выражения:
Произведение равно 1 только, если каждый из сомножителей = 1.
Следовательно: B=1 и =1.
Ответ: в первой аудитории проходят занятия по физике, во второй аудитории проходят занятия по информатике.
Минимизация функций алгебры логики
с помощью карт Карно
Карты Карно представляют собой таблицы, в каждой клетке которых записано значение функции алгебры логики на определенном наборе значений аргументов. Столбцы и строки этой таблицы пронумерованы так, что каждая клетка соответствует одной комбинации значений агументов и так, что при переходе в соседнюю клетку меняется значение только одной переменной.
| X | Y | Z | F |
Нарисуем карту Карно, соответствующую приведенной в качестве примера таблице истинности.
Карта Карно представляет собой квадрат или половинку квадрата. Количество клеток в карте равно количеству значений функции (в данном случае – 8).
Пронумеруем столбцы таблицы комбинациями значений X и Y, а строки – значениями Z. Начинать можно с любой комбинации, допустим с 00.
Обратите внимание, что при переходе из второго столбца в третий, изменяется только значение X, поэтому номер изменяется от 01 к 11.
Теперь каждой строчке таблицы истинности соответствует одна клетка карты Карно, например верхняя левая клетка – комбинации значений аргументов 000, а нижняя правая – комбинации 101. Расставив в карте Карно значения функции, соответствующие таблице истинности, получим карту, показанную на рисунке.
