Логические функции и их преобразования. законы логики

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

Законы логики

1) АA закон двойного отрицания;

2) A&BB&A коммутативность конъюнкции;

3) AVBBVA коммутативность дизъюнкции;

4) A&(B&C)(A&B)&C ассоциативность конъюнкции;

5) AV(BVC)(AVB)VC ассоциативность дизъюнкции;

6) A&(BVC)(A&B)V(A&C) дистрибутивность конъюнкции относительно дизъюнкции;

7) AV(B&C)(AVB)&(AVC) дистрибутивность дизъюнкции относительно конъюнкции;

8) A&AA

9) AVAA

10) AVAИ закон исключенного третьего;

11) A&AЛ закон непротиворечия;

12) A&ИA

13) AVИИ

14) A&ЛЛ

15) AVЛA

16) (A&B)A V B законы де Моргана;

17) (AVB)A & B

18) A => BA V B замена импликации.

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

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

Решение

Пример 2. Минимизировать функцию

Решение

При упрощении выражения использовались формулы поглощения и склеивания.

Пример 3. Найти отрицание следующего высказывания: "Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно".

Решение

Обозначим высказывания:

Y — "Урок интересный";

M — "Миша смотрит в окно";

B — "Вика смотрит в окно";

C — "Света смотрит в окно".

При упрощении выражения использовались формула замены операций и закон де Моргана.

Пример 4. Определить участника преступления, исходя из двух посылок:

1. "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";

2. "Если Иванов не участвовал, то Сидоров не участвовал".

Решение

Составим выражения:

I — "Иванов участвовал в преступлении";

P — "Петров участвовал в преступлении";

S — "Сидоров участвовал в преступлении".

Запишем посылки в виде формул:

Тогда

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

Ответ: Иванов участвовал в преступлении.

Построение логической функции по ее таблице истинностиМы научились составлять таблицу истинности для логической функции. Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z(X,Y):

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

Рассмотрим строки, где значение истинности функции Z истинно (Z=1). Функцию для этой таблицы истинности можно составить следующим образом: Z(X,Y) = ( X& Y)V(X& Y). Каждой строке, где функция истинна (равна 1), соответствует скобка, представляющая собой конъюнкцию аргументов, причем если значение аргумента О, то мы берем его с отрицанием.

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

Z(X,Y)((X& Y) VX)&(( X&Y)V Y)(XV( X& Y)) &( YV(X&Y))((XVX)&(XV Y))&(( YV X)&( YV Y))(1&(XV Y))&(( YV X)& Y) (XV Y)&(( YV X)& Y).

Проверьте полученную формулу: составьте таблицу истинности для функции Z(X,Y). Запишите правила конструирования логической функции по ее таблице истинности:

Выделить в таблице истинности те строки, в которых значение функции равно 1.

Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.

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

Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент мы берем с отрицанием.

Рандомно подобранные статьи с сайта:

Алгебра логики: Законы алгебры логики. Центр онлайн-обучения «Фоксфорд»


Похожие статьи:

  • Свойства элементарных функций алгебры логики

    Из таблицы для функции двух переменных видно, что элементарные функции типа отрицания, дизъюнкции, конъюнкции, Шеффера, Пирса и т.д. находятся в связи…

  • Логические основы эвм

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

  • Элементы математической логики

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

admin