Студопедия — Законы алгебры логики
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Законы алгебры логики






 

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

· законы идемпотентности:

o x Ù x = x

o x Ú x = x

· x Ù 1 = x

· x Ú 1 = 1

· x Ù 0 = 0

· x Ú 0 = x

· x Ù Ø x = 0 – закон противоречия

· x Ú Ø x = 1 – закон исключения третьего

· Ø Ø x = x – закон снятия двойного отрицания

· законы поглощения

o x Ù (y Ú x) = x

o x Ú (y Ù x) = x

Доказательство этих и последующих законов элементарно осуществляется с помощью построения таблиц истинности или простейших логических рассуждений.

Следующая группа законов представляет взаимосвязь между логическими операциями:

· (x º y) = (x ® y) Ù (y ® x)

· x ® y = Ø x Ú y

· законы Де Моргана

o Ø (y Ú x) = Ø y Ù Ø x

o Ø (y Ù x) = Ø y Ú Ø x

Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:

х у х | у
0 0 1
0 1 1
1 0 1
1 1 0

На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:

· Ø x = x | x

· x Ù y = (x | y) | (x | y)

Также следует отметить, что x | y = Ø (x Ù y).

К основным законам алгебры логики также относятся следующие:

· коммутативные законы

o х Ù y = y Ù х

o х Ú y = y Ú х

· дистрибутивные законы

o х Ù (y Ú z) = (х Ù y) Ú (х Ù z)

o х Ú (y Ù z) = (х Ú y) Ù (х Ú z)

· ассоциативные законы

o х Ù (y Ù z) = (х Ù y) Ù z

o х Ú (y Ú z) = (х Ú y) Ú z

Еще одним важным законом алгебры логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х Ú y) Ù z двойственной формулой будет (х Ù y) Ú z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства.

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

Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы b, если α содержит меньше букв и логических операций. Например, для формулы (Ø (x Ú y) ® x Ú y) Ù y можно записать следующую цепочку преобразований, приводящих ее к более простому виду:

(ØØ (x Ú y) Ú x Ú y) Ù y = (x Ú y Ú x Ú y) Ù y = (x Ú y) Ù y = y.

 







Дата добавления: 2015-04-16; просмотров: 737. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Именные части речи, их общие и отличительные признаки Именные части речи в русском языке — это имя существительное, имя прилагательное, имя числительное, местоимение...

Интуитивное мышление Мышление — это пси­хический процесс, обеспечивающий познание сущности предме­тов и явлений и самого субъекта...

Объект, субъект, предмет, цели и задачи управления персоналом Социальная система организации делится на две основные подсистемы: управляющую и управляемую...

Сущность, виды и функции маркетинга персонала Перснал-маркетинг является новым понятием. В мировой практике маркетинга и управления персоналом он выделился в отдельное направление лишь в начале 90-х гг.XX века...

Разработка товарной и ценовой стратегии фирмы на российском рынке хлебопродуктов В начале 1994 г. английская фирма МОНО совместно с бельгийской ПЮРАТОС приняла решение о начале совместного проекта на российском рынке. Эти фирмы ведут деятельность в сопредельных сферах производства хлебопродуктов. МОНО – крупнейший в Великобритании...

ОПРЕДЕЛЕНИЕ ЦЕНТРА ТЯЖЕСТИ ПЛОСКОЙ ФИГУРЫ Сила, с которой тело притягивается к Земле, называется силой тяжести...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия