Функции алгебры логики
Практическая работа №3
Дисциплина «Архитектура ЭВМ» специальности 230115
Решение задач булевой алгебры.
Постановка задачи.
1. Составить таблицы истинности для предложенных выражений.
2. Упростить предложенные выражения.
3. Восстановить выражения по таблицам истинности.
4. Составить логические схемы, используя таблицы истинности и логические выражения.
5. Упростить логические схемы.
6. Решение логических задач.
Цель работы. Получение и закрепление навыков работы с логическими выражениями; научиться понимать таблицы истинности и составлять их; научиться читать логические схемы.
Теоретическая часть.
Исходным понятием логики высказываний является простое высказывание. Это понятие не определяется через другие понятия, так как является базовым. Под высказыванием обычно понимают всякое повествовательно предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание называют истинным. В противном случае – ложным.
Обычно элементарные высказывания обозначают строчными буквами латинского алфавита a, b, c, x, y …, которые также являются логическими переменными. Истинные значения обозначаются буквой И или 1, а ложные – Л или 0.
Из элементарных высказываний можно составить более сложные с помощью логических связок Ø, Ù, Ú, ®, º, называемых соответственно отрицание, логическое и (конъюнкция), логическое или (дизъюнкция), логическое следствие (импликация), эквивалентность и круглых скобок (, ). Семантику логических связок можно представить с помощью таблицы истинности. В левой части этой таблицы перечисляются все возможные комбинации значений логических переменных. В правой части – соответствующие им значения новых выражений, полученных из переменных и связок.
| Х | у | Øх | х Ù у | х Ú у | х ® у | х º у |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Связки имеют следующий приоритет: Ø Ù Ú ® º. Приоритет операций, представленных логическими связками можно изменить с помощью скобок. Высказывания, построенные с помощью простых высказываний, связок и скобок, называют правильно построенными формулами или сокращённо формулами.
Замечательным свойством логики высказываний является то, что ее семантика близка к соответствующим высказываниям на естественном языке. Так, например семантика формул содержащих связки Ø и Ù практически совпадает со смыслом фраз содержащих слова «не» и «и». Однако имеются и некоторые различия. Так формула х Ú у несколько шире, чем русское «х или у». Выражение «х или у» по смыслу ближе к формуле х Ù Øу Ú Øх Ù у. Еще больше различий между семантикой формулы х ® у в логике высказываний и выражению «из х следует у». В русском языке это выражение истинно, если истинны х и у, т.е. предложение русского языка по смыслу совпадает с формулой х Ù у. Логическое следствие истинно также, если х и у ложны или х ложна, а у истинна. Логическую формулу х ® у следует интерпретировать на естественном языке так: «Если х истинна, то у тоже истинна, а остальное неизвестно».
Для любой формулы также можно построить таблицу истинности. Например, для формулы таблица истинности будет выглядеть следующим образом:
| х | у | Ø х | Ø x Ú у | Ø х Ù (Ø x Ú у) | Ø x Ù (Ø x Ú у) ® Ø x |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Очевидно, что если формула содержит n переменных, то в таблице истинности будет содержаться 2n строк. В приведенном примере формула содержит 2 переменные и 22 = 4 строки. Кроме того, данная формула истинна на любом наборе значений своих переменных. Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы будем обозначать знаком равенства =.
Законы алгебры логики
В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:
· законы идемпотентности:
o x Ù x = x
o x Ú x = x
· x Ù 1 = x
· x Ú 1 = 1
· x Ù 0 = 0
· x Ú 0 = x
· x Ù Ø x = 0 – закон противоречия
· x Ú Ø x = 1 – закон исключения третьего
· Ø Ø x = x – закон снятия двойного отрицания
· законы поглощения
o x Ù (y Ú x) = x
o x Ú (y Ù x) = x
Доказательство этих и последующих законов элементарно осуществляется с помощью построения таблиц истинности или простейших логических рассуждений.
Следующая группа законов представляет взаимосвязь между логическими операциями:
· (x º y) = (x ® y) Ù (y ® x)
· x ® y = Ø x Ú y
· законы Де Моргана
o Ø (y Ú x) = Ø y Ù Ø x
o Ø (y Ù x) = Ø y Ú Ø x
Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
| х | у | х | у |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:
· Ø x = x | x
· x Ù y = (x | y) | (x | y)
Также следует отметить, что x | y = Ø (x Ù y).
К основным законам алгебры логики также относятся следующие:
· коммутативные законы
o х Ù y = y Ù х
o х Ú y = y Ú х
· дистрибутивные законы
o х Ù (y Ú z) = (х Ù y) Ú (х Ù z)
o х Ú (y Ù z) = (х Ú y) Ù (х Ú z)
· ассоциативные законы
o х Ù (y Ù z) = (х Ù y) Ù z
o х Ú (y Ú z) = (х Ú y) Ú z
Еще одним важным законом алгебры логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х Ú y) Ù z двойственной формулой будет (х Ù y) Ú z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства.
С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул.
Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы b, если α содержит меньше букв и логических операций. Например, для формулы (Ø (x Ú y) ® x Ú y) Ù y можно записать следующую цепочку преобразований, приводящих ее к более простому виду:
(ØØ (x Ú y) Ú x Ú y) Ù y = (x Ú y Ú x Ú y) Ù y = (x Ú y) Ù y = y.
Функции алгебры логики
Значение формулы алгебры логики полностью зависит от значений входящих в нее высказываний. Поэтому такая формула может считаться функцией входящих в нее элементарных высказываний. Например, (x Ù y) ® Ø z является функцией f(x, y, z). Естественно, значения этой функции и входящих в нее элементов могут принимать значения истина или ложь. Тождественно истинные или тождественно ложные функции представляют собой константы.
Каждую функцию алгебры логики можно записать в виде формулы или представить таблицей истинности. Как уже было отмечено выше, таблица истинности для n переменных содержит 2n строк. Следовательно, каждая функция алгебры логики принимает 2n значений, состоящих из 0 или 1. Общее же число наборов значений, состоящих из 0 и 1, длины 2n равно 22n. В частности, число различных функций от одной переменной равно четырем.
| х | f1(x) | f2(x) | f3(x) | F4(x) |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
Из этой таблицы следует, что две функции являются константами f1(x) = 1 и – f2(x) = x, а остальные f3(x) = Ø x и f4(x) = 0.