4.5. Логические функции от двух переменных

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

Для двух логических переменных возможны четыре различные комбинации их значений: ТТ, TF, FT и FF. Множество комбинаций значений переменных какой-либо логической функции, при которых данная функция принимает значение истина, называется множеством истинности этой функции. Например, множество истинности для функции AND состоит из одного элемента (ТТ), тогда как для функции OR - из трех элементов (ТТ, TF, FT).

Упражнение 4.1

Самостоятельно запишите множества истинности для следующих функций: a) NAND; б) NOR; в) XOR; г) АВ; д) ˜А и е) А→В.

Существует всего 16 различных способов заполнения таблиц истинности логических функций от двух переменных. В табл. 4.8 представлены все функции указанного вида от переменных р и q. Следует отметить, что любая логическая функция от произвольного числа переменных может быть представлена в виде комбинации функций от двух переменных.

Напомним, что запись р означает: "высказывание р - истинно", а ~р - "высказывание р - ложно".

Покажем, как ищется символьная запись для функций, имеющих множества истинности, содержащие по одному элементу. Рассмотрим функцию h из табл. 4.8. Высказывание, соответствующее данной функции, истинно только тогда, когда р и q одновременно равны Т, поэтому указанная функция может быть записана как h = р ∧q или в булевой форме: h = p*q. Высказывание, соответствующее функции 0, истинно, когда р и q одновременно ложны. Поэтому о =~р ∧~q или в булевой форме: о = ~р*~q. Заметим, что высказывание о не совпадает с ~(р∧q)

Таблица 4.8. Функции от двух переменных

В качестве упражнения попробуйте, не заглядывая в книгу, дальше найти в табл. 4.8 функцию ~(р∧q). Попытайтесь также записать в символьном виде какие-либо из функций, представленных в табл. 4.8.

Две оставшиеся нерассмотренными функции, имеющие по одному элементу в своих мнбжествах истинности, обозначены в табл. 4.8 1 и п. Функция 1 равна Т только при одной комбинации значений входных переменных: TF. Это значит, что 1 истинна, когда р истинно, a q ложно, т. е. 1 = р ∧~q. Аналогично можно установить, что n = ~р∧q.

Теперь рассмотрим четыре функции от двух переменных, принимающих на одной комбинации значений р и q значение не Т как в рассмотренных выше случаях, a F. Эти функции обозначены в табл. 4.8 через b, с, е и i. В данном случае удобнее сначала искать выражение для соответствующих противоположных функций, равных Т при тех входных комбинациях, при которых исходные функции равны F, а затем с помощью отрицания этих функций получить искомую. Так, например, функция i равна F при р = q = Т. Тогда i = ~ (р∧q).

Упражнение 4.2

Самостоятельно найти функции Ь, с и е из табл. 4.8. Они представляют собой отрицания ранее рассмотренных функций. Каких именно?

Из шестнадцати таблиц истинности логических функций от двух переменных восемь мы уже рассмотрели. Со следующими двумя, а и г, разобраться довольно просто. Функция а при всех значениях р и q истинна и представляет все тавтологии, например р∨~p. Функция r всегда ложна и представляет все противоречия, например р ∧~p.

Функции d и m также элементарны. Первая из них истинна, если истинно р, и ложна, если ложно р, т. е. d = р. Функция m наоборот: истинна, если ложно р, и ложна, если истинно р; следовательно, m = ~р. По аналогии с функциями d и m легко заметить, что f = q, a k = ~q.

Итак, в табл. 4.8 остались не рассмотренными две функции g и j. Множество истинности для j состоит из двух элементов - TF и FT. Данная функция может быть выражена в следующем символьном виде: j = (р ∧~q)∨(~р∧q). Функция g может быть записана как отрицание функции j или иначе: (р ∧q)∨(~р ∧~). Отметим, что j представляет собой рассмотренную ранее операцию XOR, тогда как g - операцию IFF.

Внимательно рассмотрев табл. 4.8, можно увидеть, что она обладает определенного рода симметрией относительно середины, т. е. линии, разделяющей столбцы h и i. Столбцы, находящиеся на одинаковом расстоянии от указанной линии (h и i, g и j и т. д.), получаются друг из друга с помощью операции отрицания. Поэтому для получения всех шестнадцати функций достаточно иметь выражения лишь для восьми левых (или правых) основных функций. Остальные восемь могут быть получены с помощью отрицания основных.

Упражнение 4.3

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

Упражнение 4.4

Найдите в табл. 4.8 столбцы, соответствующие функциям р→q и р ↔q.