Алгебра логики высказываний Основные понятия
Скачать 428.51 Kb.
|
Законы алгебры логикиВ логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:
Доказательство этих и последующих законов элементарно осуществляется с помощью построения таблиц истинности или простейших логических рассуждений. Следующая группа законов представляет взаимосвязь между логическими операциями:
Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:
Также следует отметить, что x | y = (x y). К основным законам алгебры логики также относятся следующие:
Еще одним важным законом алгебры логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х y) z двойственной формулой будет (х y) z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства. С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул. Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула α проще формулы , если α содержит меньше букв и логических операций. Например, для формулы ( (x y) x y) y можно записать следующую цепочку преобразований, приводящих ее к более простому виду: ( (x y) x y) y = (x y x y) y = (x y) y = y. |
Похожие:
 | 1. «Совершенные дизъюнктивные нормальные формы (сднф) и совершенные... Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим... | | 2. Основы логики и логические основы компьютера Основы логики. Основные... Информационные процессы в живой природе, обществе и технике: получение, передача, преобразование, хранение и использование информации.... |
 | «Основные логические элементы» Данный урок является частью темы «Алгебра логики». Необходимость изучения данной темы обусловлена значением переключательных схем... | | Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика |
| Программа по дисциплине «прикладные протоколы интернет и www» Глобальные вычислительные сети: os unix – основные понятия, Internet – структура и основные понятия, аппаратное обеспечение, программное... | | Урок №47. Формы мышления. Алгебра высказываний. Цели урока Правомерно ли считать, что религия, искусство, наука – духовные истоки философии? Обоснуйте свой ответ |
| Конспект урока Тема: Алгебра логики. Решение задач с элементами алгебры логики Планируемый результат: учащиеся решат задачу на движение, используя ос решения текстовой задачи, продемонстрируют уровень усвоения... | | Реферат по информатике и икт на тему: «Логика» Что такое алгебра логики стр. 4 |
| Тема: Основные понятия математической логики Автор, к своему стыду, до сих пор иногда путает и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком... | | Программа предназначена для преподавателей, ведущих данную дисциплину,... Цель урока: закрепить основные понятия, рассматриваемые в законах механики Ньютона |
| «Волшебный компьютер» (35 часов) Свойства информации. Язык представления информации. Кодирование информации. Основные понятия логики. Понятие графов. Устройство персонального... | | Урок 1 Тема урока : Логика как наука. Основные понятия математической логики Учебный курс (рабочая программа) «Логика научного исследования» для аспирантов очной и заочной форм обучения специальностей 09. 00.... |
| Тема : Основные понятия математической логики А представляет собой двоичную запись числа 226, столбец значений аргумента в – числа 154, столбец значений аргумента с – числа 75.... | | Урок лекция План проведения урока Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной... |
| Программа по формированию навыков безопасного поведения на дорогах... Цели Помочь учащимся осознать понятия: грех, гордость, смирение на примере отрывка из Священной истории «Мытарь и Фарисей», высказываний... | | Программа по формированию навыков безопасного поведения на дорогах... Мотивы, которые побудили выбрать тему «Алгебра логики и логические элементы персонального компьютера» для создания данного комплекса... |
