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

Пусть п = 2. Существует 16 различных логических функций от двух переменных. Рассмотрим их подробно:

 

Аргу-менты

Функции

X1

X2

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

F₁ — константа 0.

F₂ — конъюнкция.

F₃ — отрицательные импликации X₁ и X₂.

F₄ — функция, повторяющая переменная X₁.

F₅ — отрицание импликации X₂ и X₁.

F₆ — переменная X₂.

F₇ — строгая дизъюнкция или отрицание эквивалентности
(неравнозначность) переменных X₁ и X₂. Значение этой функции получается поразрядным сложением двоичных переменных X₁ и X₂ по модулю 2, то есть без учета переноса в старший разряд.

F₈ — дизъюнкция.

F₉ — отрицание дизъюнкции (функция ИЛИ-НЕ); эта функция называется также функцией Пирса («стрелка» Пирс).

F₁₀ — эквивалентность.

F₁₁ — отрицание переменной X₂.

F₁₂ — импликация X₁ и X₂.

F₁₃ — отрицание X₁.

F₁₄ —импликация X₁ и X₂.

F₁₅ — отрицание конъюнкции (функция И-НЕ); эта функция называется также функцией Шеффера («штрих» Шеффера).

F₁₆ — константа 1.

С увеличением числа аргументов количество логических функций резко возрастает. Так, при п = 3 их будет уже 256. Но изучать их все нет никакой необходимости. Дело в том, что функция любого количества переменных может быть выражена через функции только двух переменных. Делается это с помощью приема суперпозиции, состоящего в том, что, во-первых, на место переменных подставляются функции, во-вторых, переменные меняются местами.

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

Вот несколько примеров функционально полных наборов:

1) F2 и F11; 2) F13 и F8; 3) F9 и F15.

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

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

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

 

Алгоритм построения таблицы истинности

1) Подсчитать n — количество переменных в формуле.

2) Определить число строк в таблице m = 2ⁿ.

3) Подсчитать количество логических операций в формуле.

4) Установить последовательность выполнения логических операций с учетом скобок и приоритетов.

5) Определить количество столбцов в таблице: число переменных плюс число операций.

6) Выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2ⁿ—1.

7) Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной
в п. 4 последовательностью.

Пример. Для формулы АÙ (BÚ BÙ C) построить таблицу
истинности.

A	B	C	_ B	_ C	B Ù C	B Ù B Ù C	АÙ (B Ú B Ù C)

 

Наборы входных переменных во избежание ошибок иногда рекомендуют перечислять следующим образом:

1) определить количество наборов входных переменных;

2) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю — единицами;

3) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами нулей или единиц, начиная с группы нулей;

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

Процедура составления таблиц истинности может быть существенно сокращена, если воспользоваться следующим приемом.

Пример. Для получаем:

Законы логики высказываний

 

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

 

⇐ Предыдущая14151617181920212223Следующая ⇒

Поделиться:

Популярное:

1. B. Функции языка как театральной коммуникативной системы
2. I. КРАТКИЕ СВЕДЕНИЯ О СТРОЕНИИ И ФУНКЦИИ МИОКАРДА
3. II. Психологические и космологические предпосылки к тексту
4. II. ЭВОЛЮЦИЯ ДВУХ РАЗНЫХ ПОДХОДОВ
5. III. Вегетативные функции НС.
6. IV. Математическая двухзонная модель пожара в здании
7. Xlabel('Значения x'); ylabel('Значения функции'), grid
8. а, г – пресс канты с двухсторонней «прибылью», б – пресс-канты с односторонней «прибылью», в – пресс-канты без «прибыли»
9. А, г – пресс канты с двухсторонней «прибылью», б – пресс-канты с односторонней «прибылью», в – пресс-канты без «прибыли»
10. Адвербиальные фразеологические единицы с подчинительной структурой
11. Анализ структуры и выполняемые функции информационной подсистемы «Кадры» ОГУ
12. Анатомические и физиологические аспекты