Приоритет основных логических операций

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.

Ответ: в первой аудитории проходят занятия по физике, во второй аудитории проходят занятия по информатике.

Минимизация функций алгебры логики
с помощью карт Карно

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

Нарисуем карту Карно, соответ­ству­ющую приве­ден­ной в качестве примера таблице истинности.

Карта Карно представляет собой квадрат или поло­вин­­ку квадрата. Количество клеток в карте равно коли­чес­тву значений функции (в данном случае – 8).

Пронумеруем столбцы таблицы комбинациями зна­че­ний X и Y, а строки – зна­чениями Z. Начинать можно с любой комбинации, допустим с 00.

Обратите внимание, что при переходе из второго столбца в третий, из­ме­ня­ет­ся только значение X, поэтому номер изменяется от 01 к 11.

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