Равносильные преобразования формул

Используя равносильности I, II и III групп можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.

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

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

Определение. Функцией алгебры логики n переменных (или функцией Буля) называется функция n переменных, где каждая переменная принимает два значения: 0 и 1, и при этом функция может принимать только одно из двух значений: 0 или 1.

Тождественно истинные и тождественно ложные формулы алгебры логики представляют собой

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

Рассмотрим таблицу истинности для различных функций одной переменной.

Из этой таблицы следует, что две функции одной переменной будут постоянными: f₁(x) º 1. f₄(x) º0, а f₂(х) º x. и fз(х) º .

Таблица истинности для всевозможных функций двух переменных имеет вид: