Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Формулы алгебры логикиОпределение 3.1. Пусть - множество исходных функций. Символы переменных , …, будем считать формулами глубины 0. Формула F имеет глубину k+ 1, если F имеет вид , где ÎS, - число аргументов функции , - формулы, максимальная из глубин которых равна k. Все формулы называются подформулами F; - называется внешней или главной операцией формулы F. Все подформулы формул также называются подформулами F. Например, (, , ) - это формула глубины 1, а - формула глубины 3, содержащая одну подформулу глубины 2 и две подформулы глубины 1. В дальнейшем формулы будут иметь более привычный вид, при котором знаки функций стоят между аргументами. Например, если в предыдущем примере обозначает дизъюнкцию, - конъюнкцию, - сложение по модулю 2, то приведенная формула имеет вид: ( Ú ) Å( &( Å )). Всякая формула, выражающая функцию f как суперпозицию других функций, задает способ ее вычисления. Этот способ определяется следующим правилом: формулу можно вычислить, только если вычислены значения всех ее подформул. Вычислим значение предыдущей формулы на наборе =1, =1, = 0. Получим Ú =1, Å = 0, &( Å ) = 1& 0 = 0, ( Ú ) Å( &( Å )) = 1Å 0 =1. Так же как для алгебраических выражений для записи логических формул используют соглашение о приоритете операций. Перечислим приоритет логических операций в порядке его убывания: Ø, Ù, Ú, ®, ~. Операции |, ¯ имеют тот же приоритет, что и Ù, а Å - тот же приоритет, что и ~. Таким образом в формуле без скобок сначала выполняется Ø, затем Ù и т.д. Формула каждому набору значений аргументов ставит в соответствие значение функции. Вычисляя формулу на всех наборах значений переменных, можно построить таблицу истинности функции. Пример 3.1. Составим таблицу истинности для формулы Ø (А Ù В Ú С).
В отличие от табличного задания, представление функции формулой не единственно. Например, функцию штрих Шеффера можно представить формулами: | = Ú и | = Ø( & ); а функцию стрелка Пирса - формулами: ¯ = & и ¯ = Ø( Ú ). Определение 3.2. Формула, истинная при всех возможных значениях переменных, называется общезначимой или тавтологией. Определение 3.3. Формула, ложная при всех возможных значениях переменных, называется невыполнимой или противоречием. Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными. Эквивалентность формул обозначается знаком равенства =, т.е. | = Ú = Ø( & ). Для проверки эквивалентности формул существует стандартный способ: для каждой формулы строится таблица истинности, а затем две таблицы сравниваются. Этот метод требует 2× вычислений для формул от п переменных. Существуют и другие методы установления эквивалентности формул и получения новых формул, эквивалентных исходной. Пример 3.2. Проверить эквивалентность формул и . Составим для этих формул таблицу истинности.
Формулы не эквивалентны, так как 3-й и 6-й столбцы таблицы не совпадают. Пример 3.3. Проверить эквивалентность формул А ~ В и . Составим для этих формул таблицы истинности. Формулы эквивалентны, так как 3-й и 8-й столбцы таблицы совпадают.
|