рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

ЛОГИКА ВЫСКАЗЫВАНИЙ

ЛОГИКА ВЫСКАЗЫВАНИЙ - раздел Философия, Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА Математическая Логика Изучает Базовые Понятия Синтак­сиса (Формы) И Семантики...

Математическая логика изучает базовые понятия синтак­сиса (формы) и семантики (содержания) естественного языка. Рассмотрим три крупных направления исследований в матема­тической логике — логику высказываний, логику предикатов и теорию доказательств. Эти направления потребуются при изучении кибернетических и интеллектуальных систем.

Известно, что в исчислении высказываний теоремами являют­ся общезначимые формулы, поэтому автоматизация доказатель­ства осуществляется в виде проверки общезначимости формул с помощью таблиц истинности. Проверка истинности формул про­изводится для любого конечного набора значений переменных. Таким образом, можно алгоритмизировать процесс доказательства теорем, но не процесс вывода теорем из аксиом.

 

Определения

Определение 1. Высказыванием называется повество­вательное предложение (текст) естественного языка, о котором имеет смысл говорить истинно оно или ложно.

 

Например, «студент Петров присутствует на лекции», «эта стена белая», «33 = 28» и т.д.

 

Предложение «Город х стоит на реке у» не явля­ется высказыванием, пока не заданы х и у, так как здесь нельзя определить истина это или ложь.

Из данных высказываний можно составлять новые, сложные высказывания с помощью так называемых логических опера­ций.

Истинность значений сложных высказываний определяет­ся только истинностью значений составляющих высказываний, а не их смыслом. Простейшие высказывания, в которых не вы­деляются части, являющиеся высказываниями, будем обозна­чать прописными латинскими буквами А, В, ..., Р, ... и называть атомарными.

Определение 2. Отрицанием высказывания Р называ­ется высказывание, истинное тогда и только тогда, когда Р лож­но. Отрицание Р обозначается ]Р или Р и читается «не Р».

Отрицание высказывания определяется табл. 1.

Таблица истинности отрицания

P
И Л
Л И

В естественном языке отрицание соответствует составлению из высказывания Р нового высказывания «неверно, что Р», или «не Р».

Определение 3. Конъюнкцией двух высказываний Р и Q называется высказывание, истинное тогда и только тогда, ко­гда истинны оба высказывания. Конъюнкция Р и Q обозначается Р & Q или Р Q и читается «Р и Q».

Конъюнкция определяется

Таблица истинности конъюнкции

P Q
И И И
И Л Л
Л И Л
Л Л Л

В естественном языке конъюнкция соответствует соединению высказываний союзом «и».

Определение 4. Дизъюнкцией двух высказываний Р и Q называется высказывание ложное тогда и только тогда, когда ложны оба эти высказывания.

Дизъюнкция высказываний Р и Q обозначается Р V Q и читается «Р или Q».

Дизъюнкция определяется табл. 3.

Таблица 3.

Таблица истинности конъюнкции

P Q
И И И
И Л И
Л И И
Л Л Л

В естественном языке дизъюнкция соответствует соединению высказываний союзом «или» в неразделительном смысле.

Рассмотрим теперь сложное высказывание, которое в есте­ственном языке выражают, например, фразой «если Р, то Q» (или «из Р следует Q», или «Р влечет Q»). Жизненный опыт подсказывает, что истинность этого высказывания должна обо­значать следующее:

если Р истинно, Q «обязано» быть истин­ным (следовать из Р);

если же Р ложно, то на Q нет ограниче­ний, оно может быть как истинным, так и ложным (из ложного утверждения ничего не следует).

Значит, «из Р следует Q» ложно в единственном случае: Р истинно, Q ложно.

Следующие высказывания служат примерами:

1) если 0 = 0, то 1 = 1;

2) если 0 = 1, то 0 = 0;

3) если 0 = 0, то 0 = 1;

4) если 0 = 1, то 1 = 2.

Первое утверждение истинно, так как, используя равенство 0 = 0 и другие свойства чисел, можно вывести 1 = 1, прибавляя по единице к обеим частям равенства 0 = 0.

Второе утверждение тоже естественно считать истинным, так как, умножая на нуль обе части равенства 0 = 1, получим 0 = 0.

Третье приходится считать ложным, так как исходя из ис­тинного равенства 0 = 0 с помощью умозаключений никогда не придем к ложному.

Четвертое естественно считать истинным. Прибавляя к обе­им частям равенства 0 = 1 по 1, получим 1 = 2.

Используя оборот «если Р, то Q» как логическую операцию, определим ее следующим образом.

Определение 5. Импликацией двух высказываний Р и Q называется высказывание ложное тогда и только тогда, когда Р истинно, a Q ложно.

Импликация высказываний обозначается Р => Q, или Р Q и читается: «Р влечет Q», или «если Р то Q», или «из Р следует Q», или «пусть Р, тогда Q», или «Р является достаточным для Q», или «Q является необходимым для Р».

Высказывание Р называется посылкой импликации, a Q -заключением.

Таблица 4. Таблица истинности импликации и эквивалентности

P Q
И И И И
И Л Л Л
Л И И Л
Л Л И И

Определение 6. Эквивалентностью двух высказыва­ний Р и Q называется высказывание, истинное тогда и только тогда, когда истинности Р и Q совпадают. Эквивалентность обо­значается Р ~ Q и читается: «Р эквивалентно Q», или «Р тогда и только тогда, когда Q», или «Р является необходимым и доста­точным для Q».

 

Формулы логики высказываний

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

Определение 7. Алфавитом называется любое непустое множество. Элементы этого множества называются символа­ми (буквами) данного алфавита.

Определение 8. Словом в данном алфавите называется произвольная конечная последовательность символов (возмож­но, пустая).

Слово а называется подсловом слова b, если b = b1 a b2 для некоторых слов b1 и b2.

Всякое подмножество слов данного алфавита называется языком в этом алфавите.

Рассмотрим язык логики высказываний, т. е. подмножество слов в некотором выделенном алфавите. Слова в языке логики высказываний принято называть формулами логики высказыва­ний. Эти формулы используются для моделирования высказы­ваний.

Определение 9. Пусть известно.

1. Алфавит логики высказываний содержит следующие символы: высказывателъные переменные Х1, Х2, логи­ческие связки &, , , =>, ~; символы скобок (, ), которые в дальнейшем будут играть разные роли.

2. Всякая высказывательная переменная есть формула, кото­рая называется атомарной.

3. Если а — формула, то (а) — формула. Если а и b — форму­лы, то (а&b), (а V b), (а => b), (а ~ b) — формулы.

4. Других правил образования формул нет.

Замечание 1. Вместо высказывательных переменных Х1, . . ., Хп, ... иногда удобно пользоваться прописными латинскими буквами без индексов.

Пример 1. Слово (((А)&В) => (BА)) — формула.

Слово (А & В) => В A не является формулой (нет скобок).

Слово ((АВ) => (В A)) — не формула, так как знак не бинарная связка.

Замечание 2. Удобно при записи формул по умолчанию опус­кать внешние скобки и скобки при отрицании высказывательных пере­менных, например формула из примера 1:

(А&В) => (В A).

Определение 10. Логические связки в логике высказыва­ний задают алгебраические операции на множестве Ф всех вы­сказываний.

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

В связи с этим логика высказыва­ний — алгебра с пятью алгебраическими операциями (Ф, &, V, =>, ~, ), которая называется алгеброй логики высказываний.

 

Обсудим синтаксис, семантику и прагматику языка логики высказываний.

Синтаксис языка логики высказываний изучает правиль­ность написания формул (слов языка), согласно определению формулы логики высказываний. Нетрудно предложить алгоритм отыскания ошибок в слове, например, указать на символ не из алфавита логики высказываний, на отсутствие необходи­мого или присутствие лишнего операнда логической операции, на отсутствие или несоответствие скобок в слове и т. д.

Семантика языка логики высказываний изучает смысл фор­мул (слов языка) с точки зрения их оценивания на истинность. Вопросы семантики часто решаются с помощью таблиц истин­ности формул.

 

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

 

Правила преобразования формул

Определение 11. Пусть а и b — две формулы, зависящие от одного и того же множества высказывательных переменных.

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

Равносильность формул а и b логики высказываний будем обозначать a ≡ b, так же как равносильность формул в элемен­тарной алгебре, например a3 — b3 ≡ (a - b)(a2 + ab + b ).

Пояснение. Оценка переменных — набор истинностных зна­чений данных переменных.

Равносильность формул имеет свой алгебраический аналог в тождественном равенстве алгебраических выражений.

Замечание. Нужно различать символы «≡» и «~».

Символ «~» является символом логической операции формального языка (это необходимо и достаточно).

Символ «≡» является метасимволом. Он не принадлежит алфавиту языка логики высказываний и говорит о равносильности слов с точки зрения их семантики.

 

Основные равносильности.

Для любых формул a, b, c справедливы следующие равносильности.

1. a&b=b&a (коммутативность операции &).

2. a&a = а (идемпотентность операции &).

3. а & (b & с) = (а & b) & с (ассоциативность операции &).

4. а b = b а (коммутативность операции ).

5. а а = а (идемпотентность операции ).

6. а (b с) = (а b) с (ассоциативность операции ).

7. a(b&с) = (аb)&(aс) (дистрибутивность операции относительно операции &).

8. a&(bс) = (a&b)(а&с) (дистрибутивность операции & относительно операции ).

9. а & (а b) = а (первый закон поглощения).

10. а (а&b) = а (второй закон поглощения).

11. а = а (снятие двойного отрицания).

12. (a&b) = ab (первый закон де Моргана).

13. (а b) = а &b (второй закон де Моргана).

14. а = (a&b)(а& b) (первая формула расщепления).

15. а = (ab)&(аb) (вторая формула расщепления).

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

Еще одна группа равносильностей показывает, что одни связ­ки могут быть выражены через другие.

16. а ~ b ≡ (а b)&(bа) ≡ (a&b) (a&b).

17. a=>b≡ab≡(a&b).

18. ab≡ab≡(a&b).

19. a&b≡(a =>b) ≡(a&b).

Рассмотрим доказательство приведенных равносильностей на примерах тождеств 8, 10, 15. При этом в методических целях приведем три различных способа доказательства.

Пусть в тождестве 8 формулы a, b, с — атомарные, т. е. a = А, b = B, с = С.

Таблица 6

Таблица истинности равносильных формул

A B C
И И И И И И И И
И И Л И И Л И И
И Л И И И Л И И
И Л Л Л Л Л Л Л
Л И И И Л Л Л Л
Л И Л И Л Л Л Л
Л Л И И Л Л Л Л
Л Л Л Л Л Л Л Л

 

Рассмотрим табл. 6. Пятый и восьмой столбцы в таблице совпадают, следовательно, тождество доказано. Этот способ до­казательства равносильности назовем табличным.

 

Теперь докажем тождество 10 (второй закон поглощения) пу­тем логических рассуждений. Этот способ называется логиче­ским. Он имеет два хода рассуждения: «слева—направо» и «справа — налево».

Ход «слева —направо». Пусть в тождестве 10 слева будет ложь, т.е. а (а&b) = Л. Тогда по определению дизъюнкции будет: а = Л и (а&b) = Л. Тем самым получили, что справа в тождестве 10 имеем ложь: а = Л.

Ход «справа— налево». Пусть в тождестве 10 справа будет ложь, т. е. a = Л. Тогда для левой части тождества 10 имеем ложь. В самом деле (а&b) = Л. Тем самым а (а&b) = Л.

Тождество 10 полностью доказано. Рассматривать отдельно случай, когда слева и справа в данном тождестве истина нет необходимости, так как его доказательство можно провести рас­суждением от противного и использованием уже доказанного.

Например, пусть слева в тождестве — истина, тогда и спра­ва будет истина, так как в противном случае, если справа бу­дет ложь, то, по доказанному, слева будет ложь. А это проти­воречит предположению. Аналогично рассматривается случай «справа- налево».

Итак, в логическом способе доказательства равносильности достаточно рассматривать один случай — или для истины, или для лжи, но обязательно в два хода: «слева — направо» и «спра­ва— налево».

 

Теперь докажем тождество 15 (вторая формула расщепле­ния) третьим способом, который назовем алгебраическим.

Суть способа состоит в использовании уже доказанных равносильностей для преобразования левой и правой частей тожде­ства к одному и тому же виду.

Рассмотрим правую часть тождества 15. Воспользуемся тож­деством 7, которое предполагаем доказанным. Тогда вынесем а за скобки, будем иметь (ab)&(аb)≡а(b&b) ≡ а, так как (b&b) ≡Л.

Тем самым правая часть тождества 15 преобразована в левую и равносильность доказана.

 

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

Теорема 1 (правило равносильных добавлений и удалений формул).

Если а, b и с — произвольные формулы, то следующие равносильности выполняются и не выполняются одновременно:

a ≡ b; a ≡ b;

a&с ≡ b&с; с&a ≡с&b;

aс≡bс; сa≡ cb;

a => с≡ b => с; с => a ≡ с =b;
Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ ЭКОНОМИКИ УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ... ИЭУИС...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ЛОГИКА ВЫСКАЗЫВАНИЙ

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Предмет дискретной математики
Предмет дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур, в то время как классическая (непрерывная) математика изучает свойства объ

Изоморфизм
Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действуе

Упражнения
1. Докажите, что изоморфное отображение всегда изотонно, а обратное утверждение неверно. 2. Запишите на языке множеств свою группу. 3. Запишите на языке множеств предметы, которые

Множество и элементы множества
В настоящее время существующие теории множеств различаются парадигматикой (системой взглядов) концептуального базиса и логических средств. Так, в качестве примера, можем привести две противоположны

Конечные и бесконечные множества
То, из чего состоит множество, т.е. объекты, образующие множество, называется его элементами. Элементы множества различны и отличаются друг от друга. Как видно из приведенных пример

Мощность множества
Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n

А1A2A3| + … + |А1A2A3| + … + |А1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|.
Конечное множество А имеет мощность k, если оно равномощно отрезку 1.. k;:

Подмножество, собственное подмножество
После того как введено понятие множества, возникает задача конструирования новых множеств из уже имеющихся, то есть определить операции над множествами. Множество М',

Символический язык содержательных теорий множеств
В процессе изучения курса будем различать объектный язык теории множеств и метаязык, средствами которого изучается объектный язык. Под языком теории множеств будем понимать реляцион

Доказательство
Множество В бесконечно, значит,

Добавление и удаление элементов
Если А — множество, а х — элемент, причем , то элемент

Ограниченные множества. Границы множеств
Пусть на некотором множестве X задана числовая функция f(х). Верхней гранью (границей) функции f(х) называется такое число

Точная верхняя (нижняя) граница
Совокупность всех верхних границ Е обозначается через Еs, всех нижних границ - через Еi. В случа

Точная верхняя (нижняя) граница множества
Если элемент z принадлежит пересечению множества E и множеству всех его верхних границ Es (соответственно нижних г

Основные свойства верхних и нижних границ
Пусть X - частично упорядоченное множество. 1. Если , то

Множество с атрибутивной точки зрения
Агрегатная точка зрения, в отличие от атрибутивной, является логически несостоятельной в том плане, что она приводит к парадоксам типа Рассела и Кантора (см. ниже). В рамках атрибутивной т

Структура
Частично упорядоченное множество X называется структурой, если в нем любое двухэлементное множество

Покрытие и разбиение множеств
Разбиением множества А называется семейство Аi

Бинарные отношения
Последовательность длины п, члены которой суть а1, .... аn, будем обозначать через {а1, .... а

Свойства бинарных отношений
Бинарное отношение R на множестве Хобладает следующими свойствами: (а) рефлексивно, если хRх

Тернарные отношения
Декартовым произведением XY

N-арные отношения
По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение X

Отображения
Отображения – это некоторые связи между элементами множеств. Простейшими примерами отношений являются отношения принадлежности х

Соответствие
ПодмножествоSдекартового произведения называетсяn-арным соответствиeмэлементов множествMi. Формально

Функция
В основе всех разделов дискретной математики лежит понятие функции. Пусть Х —

Представление функции в терминах отношений
Функцией называется бинарное отношение f, если из и

Инъекция, сюръекция, биекция
При использовании термина «отображение» различают отображение ХвY и отображение Х на Y

Обратная функция
Для произвольных , определим

Частично упорядоченные множества
Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка

Минимизации представления множества
Используя эти законы, рассмотрим задачу минимизации представления множества М с помощью операций

Перестановки
Дано множество A. Пусть A – конечное множество, состоящее из n элементов A = {a1, a2, …, a

Перестановки с повторениями
Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n1, n2, … ,nk

Размещения
Кортежи длины k (1≤k≤n), состоящие из различных элементов n-элементного множества A (кортежи отличаются од

Размещения с повторениями
Пусть во множестве A имеются одинаковые (повторяющиеся) элементы. Размещениями с повторениями из n элементов по k назы

Упорядоченное размещение
Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два

Сочетания
Из m-элементного множества A построим упорядоченное множество длины n, элементы которого являются размещениями с одними и тем

Сочетания с повторениями
Полученные формулы справедливы только, когда в множестве A нет одинаковых элементов. Пусть имеются элементы n видов и из них составляется кортеж из

Метод производящий функций
Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств. Исходным пунктом являются последовательность {ai} комбинатор

Алгебраическая система
Алгебраической системой A называется совокупность ‹M,O,R›, первая составляющая которой M есть непустое множество, вторая компонента O – множество

Замыкание и подалгебры
Подмножество называется замкнутым относительно операции φ, если

Алгебры с одной бинарной операцией
Пусть на множестве М задана одна бинарная операция. Рассмотрим порождаемые ею алгебры, но предварительно рассмотрим некоторые свойства бинарных операций. Бинарная о

Группоид
Алгебра вида <М, f2>называется группоидом. Если f2 — операция типа умножения (

Фактор-множества и фактор-алгебра
Если отношение R обладает свойствами: рефлексивное симметричное транзитивное, т.е. является отношением эквивалентности (~ или ≡ или Е) на множестве M

Целые числа по модулю m
Дано кольцо целых чисел <Z; +, >. Напомним. Алгебра <М,

Конгруэнции
Конгруэнцией на алгебре A = <A; Σ> (Σ – сигнатура алгебры состоит только из функциональных символов) называется такое отношение эквивалентности

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Графы - математические объекты. Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование о

Граф, вершина, ребро
Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что

Соответствие
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, ко

Неориентированный граф
Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориен

Инцидентность, смешанный граф
Если ребро е имеет вид {и, v } или <и, v>, то будем говорить, что ребро е инцидентно вер

Обратное соответствие
Поскольку представляет собой множество таких вершин

Изоморфизм графов
Два графа G1 = <V1, E1> и G2 = <V2, E2> изоморфны (G

Путь, ориентированный маршрут
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в котор

Смежные дуги, смежные вершины, степень вершины
Дуги а = (хi, хj), хi ≠ хj, имеющие общие концевые вершины, н

Связность
Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны. Теорема.

Граф со взвешенными дугами
Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую на

Матрица сильной связности.
Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 д

ДЕРЕВЬЯ
Деревья важны не только потому, что они находят приложения в различных областях знаний, но и Вилу особого положения их в самой теории графов. Последнее вызвано предельной простотой строения деревье

Следствие 1 В любом нетривиальном дереве имеются по крайней мере две висячие вершины.
Доказательство Рассмотрим дерево G(V, Е). Дерево — связный граф, следовательно,

Теорема
Центр свободного дерева состоит из одной вершины или из двух смежных вершин: Z(G) = 0&k(G) = 1 → С(G) = К1

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

Доказательство
1. Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем: v

Упорядоченные деревья
Множества Т1,.. ., Тk в эквивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев Т1,.. .,

Бинарные деревья
Бинарное (или двоичное) дерево - это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев - левого и правого. Бинарное дерево не яв

Представление свободных деревьев
Для представления деревьев можно использовать те же приёмы, что и для представления графов общего вида — матрицы смежности и инциденций, списки смежности и другие. Но используя особенные свойства д

End for
  Обоснование Код Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево

Представление бинарных деревьев
Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Для потомков одного узла (братьев) упорядоченного ордерева определено отно

Основные логические функции
Обозначим через E2 = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной мате

Булева функция.
Булевой функцией от n аргументов x1, x2, … ,xn, называется функция f из n-ой степени множества

Двухэлементная булева алгебра.
Рассмотрим множество Во = {0,1} и определим на нем операции , согласно таблицам ист

Таблицы булевых функций
Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2n строк. В первом столбце перечисляются все наборы из B

F5 – повторение по y
f6 – сумма по модулю 2 f7

Порядок выполнения операций
Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. Соглашения относительно расстановки ско

Эквивалентность формул
Различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул. Формулы φ(x1,..., xn) и

Замечание
1. Формула φ тождественно ложна тогда и только тогда, когда неφ тождественно истинна (|=неφ ); 2. Формула φ

Фактор-алгебра алгебры формул
Обозначим через Фn множество всех формул алгебры логики с переменными из множества {х1, х2, ... , хn}.

Определение
Если х — логическая переменная, , то выражение

Алгоритм приведения формулы к ДНФ.
1. Выразить все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалентности

Совершенные ДНФ (СДНФ) и КНФ (СКНФ).
Пусть (x1,..., xn) — набор логических переменных, Δ = (δ1,,.., δп) — набор нулей и

Первая теорема Шеннона
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле φ, предварительно рассмотрим разложения булевой функции f(x1, х2

Вторая теорема Шеннона
В силу принципа двойственности для булевых алгебр справедлива Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f(x1, х2,...

Функциональная полнота
Теорема(о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f

Алгоритм нахождения СДНФ.
Для нахождения СДНФ данную формулу нужно привести сначала к ДНФ, а затем преобразовать ее конъюнкты в конституенты единицы с помощью следующих действий: а) если в конъюнкт входит некоторая

Метод Квайна
Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие триоперации: - операция полного склеивания -

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

Системы булевых функций
Пусть даны булевы функции f(g1, g2, …, gm) и g1(x1, x2, …, xn), g2(x1

Базис Жегалкина.
Примерю Рассмотрим систему . Она является полной, так как любая функция из стандартного базиса выражается чере

Теорема Поста
Теорема Поста устанавливает необходимые и достаточные условия полноты системы булевых функций. (Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu

Доказательство.
Необходимость. От противного. Пусть и

Алгебра Жегалкина
Сумма по модулю 2, конъюнкция и константы 0 и 1 образуют функционально полную систему, т.е. образуют алгебру - алгебру Жегалкина. A = <FB,

Определение предиката
Пусть Х1, Х2, ..., Хп произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных вы

Применение предикатов в алгебре
Рассмотрим предикаты, в которых свободной является лишь одна переменная, которую обозначим через х, и обсудим применение предикатов в алгебре. Типичным приме

Булева алгебра предикатов
Так как к предикатам можно применять логические операции, то для них справедливы основные законы булевой алгебры. Теорема. (Свойства логических операций для предикатов). Мн

F↔G=(F→G)(G→F), F→G=неFG.
2. Использовать закон ненеF=F, законы де Моргана: не(F

Исчисление предикатов
Исчисление предикатов называют еще теорий первого порядка. В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимост

Следование и эквиваленция
Высказывательная форма Q2 следу­ет из высказывательной формы Q1, если импликация Q1→Q2 об­ращается в истинное выс

Принятые обозначения
Символы «порядка не более». При сравнении скорости роста двух функций f(n) и g(n) (с неотрицательными значениями) очень удобны следующи

Метаобозначения
Обозна-чения Содержание Пример ИЛИ

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги