Составление таблицы истинности
Логика таблицы истинности – это способ (порядок) описания соответствия между всеми возможными наборами значений входящих в логическую функцию переменных и значениями функции.
Таблица истинности служит для описания логической функции (это один из способов задать логическую функцию).
Логической функцией называется функция, значение которой, как и значения входящих в нее переменных (аргументов, параметров), выражает логическую истинность (в случае классической двузначной логики они принимают значения «истина» или «ложь»).
Таблица истинности функции формируется в следующем порядке:
- Определяется число строк. В случае двузначной логики – это два в степени, равной числу переменных, плюс одна строка на заголовки. Например, таблица функции двух логических переменных будет содержать пять строк: заголовок и по одной строке на каждый из четырех (2^2=4) возможных наборов значений переменных (00, 01, 10, 11). Таблица функции трех логических переменных будет содержать девять строк, четырех – 17 и т.д.
- Определяется число столбцов. Первые n столбцов отводятся под запись наборов аргументов. Каждый из следующих столбцов служит для записи результата логической операции (в соответствии с установленными приоритетами их выполнения), причем в последнем из столбцов формируется значение функции.
- Записываются наборы значений аргументов. Чтобы не запутаться и не пропустить ни один набор, можно воспользоваться следующим способом: первый столбец мысленно делится на 2 равные части (например, если планируется 16 наборов – по 8 наборов). В первую половину записываются 0, во вторую – 1. Второй столбец делится на 4 равные части (т.е. каждая половина, выделенная в первом столбце, делится пополам). В эти части записывают по очереди: 0, 1, 0, 1 (т. е. в первую четверть – только 0, во вторую – только 1 и т.д.). Таким образом, получают все возможные комбинации первых двух аргументов. Далее третий столбец делится на 8 частей и т.д., до тех пор, пока каждая часть не будет состоять из всего одного набора: в последнем из столбцов аргументов чередование 0 и 1 будет происходить на каждой из строк.
- Для каждого набора аргументов вычисляют результаты логических операций – последовательно, в порядке приоритетов (учитывая, что последующие логические операции могут использовать результаты предыдущих) – до тех пор, пока таблица не будет заполнена целиком (т.е. в последнем столбце не будут вычислены значения функции для каждого набора аргументов).
Логические функции
В алгебре логики используется два базовых понятия:
- истинность,
- ложность.
В роли логических переменных выступают высказывания.
Под высказыванием понимают предложение, для которого можно определить, истинно оно или ложно (но не то и другое одновременно).
В записи высказывания могут использоваться:
- слова естественного языка,
- математические, физические, химические и другие знаки.
Соединив два числовых выражения с помощью знаков равенства или неравенства, можно получить высказывание. Сами по себе числовые выражения не являются высказыванием.
Например, «3+3» - это не высказывание, т. к. для него нельзя определить истинность или ложность; «3+3=6» - это истинное высказывание, а «3+3 >11» - ложное высказывание.
Простое (элементарное) высказывание – это высказывание, никакая из частей которого сама не является высказыванием.
Простые высказывания в формулах обозначают заглавными буквами латинского алфавита – A, B, C… Вопрос определения истинности или ложности элементарных высказываний находится вне предмета алгебры логики. Алгебра логики рассматривает такие высказывания как неделимую целостность.
Из простых высказываний могут быть получены сложные высказывания (путем применения логических операций НЕ, И, ИЛИ, ЕСЛИ … ТО … и других). Сложное высказывание можно трактовать как функцию f от n переменных, где n – число входящих в сложное высказывание простых.
Две логические функции называют равными, если на всех возможных аргументных наборах они имеют одинаковые значения.
Если функция f(A) принимает значения, совпадающие со значением аргумента А, ее называют функцией повторения.
Базовый набор логических функций:
- логическое отрицание (инверсия, функция НЕ). Это функция от одного аргумента, которая принимает значение, противоположное значению аргумента. Если аргумент истинный, то функция отрицания будет иметь ложное значение; если аргумент ложный, функция будет истинной;
- логическое сложение (дизъюнкция, логическое ИЛИ). Это функция двух аргументов, которая принимает ложное значение в единственном случае – если оба ее аргумента ложны. В остальных трех случаях (когда оба аргумента истинны; когда первый истинен, второй ложен; когда первый ложен, второй истинен) функция принимает значение истины;
- логическое умножение (конъюнкция, логическое И). Это функция двух аргументов, которая принимает истинное значение в единственном случае – если оба ее аргумента истинны. В остальных трех случаях (когда оба аргумента ложны; когда первый истинен, второй ложен; когда первый ложен, второй истинен) функция принимает значение «ложь»;
- импликация (логическое следование). Это функция двух переменных, которая принимает ложное значение в единственном случае – если первый аргумент истинен, а второй ложен. Трактовка таблицы истинности следующая: из ложного высказывания может быть как истинное, так и ложное следствие, а из истинного – только истинное следствие;
- эквивалентность (равнозначность). Эта функция двух аргументов имеет два ложных значения (если значения аргументов не совпадают – первый ложный, второй истинный или наоборот) и два истинных (оба истинны или оба ложны);
- стрелка Пирса (ИЛИ-НЕ). Это функция двух аргументов, которая принимает истинное значение только тогда, когда оба аргумента ложны (противоположна функции ИЛИ, является ее отрицанием);
- штрих Шеффера (И-НЕ, несовместимость). Это функция двух аргументов, которая принимает ложное значение, только если истинны оба аргумента (противоположна функции И, является ее отрицанием).
