Матлогика конспект

МатЛогика.

1.  Понятие высказывания. Примеры.

Высказывание – это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Истинность или ложность – это значение истинности или истинностное значение.

Это утверждение ложно – НЕ высказывание (внутренне противоречиво)

Я готов к экзамену по дискретной математике – высказывание

Высказывания обозначаются буквами латинского алфавита.

2.  Отрицание, конъюнкция, дизъюнкция. Определение. Примеры.

Высказывания бывают простые (не содержащие связок и, или, нет, если … то, только если, и тогда, и только тогда) и сложные (содержащие связки).

Пусть даны простые высказывания:

p: Дед Мазай собирал зайцев.

q: Мальчики-колокольчики веселые ребята.

Сложное высказывание

Дед Мазай собирал зайцев и мальчики-колокольчики веселые ребята.

состоит из двух частей, объединенных связкой и.

Символически может быть записано: p и q , p ᴧ q .

Символ ᴧ обозначает слово и на языке символических выражений и это выражение называется конъюнкцией высказываний p и q.

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

Высказывание

Дед Мазай собирал зайцев или мальчики-колокольчики веселые ребята.

состоит из двух частей, объединенных связкой или.

Символически может быть записано: p или q , p v q .

Символ ᴧ обозначает слово или на языке символических выражений и это выражение называется дизъюнкцией высказываний p и q.

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

Так же существует опровержение (отрицание) высказывания обозначается:

~p

Таким образом, это высказывание будет звучать так: «Дед Мазай не собирал зайцев».

Опровержение – это высказывание, чье истинное значение строго противоположно значению p.

3.  Импликация. Определение. Примеры.

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

Пример: Если целое число равно 4, то его квадрат равен 16.

То есть, это высказывание истинно тогда и только тогда, когда и А и В ложны, либо истинны.

Так же нужно помнить, что это не является никаким показателем причинно-следственной связи и зависит только от истинности или ложности составных частей.

Если дед Мазай собирал зайцев, то мальчики-зайчики веселые ребята.

Высказывание вида (p → q) ᴧ (q → p)обозначается <-> и называется эквиваленцией. Она истинна только в том случае, когда p и q имеют истинностные значения.

4.  Пропозициональные переменные. Правила построения формул. Примеры.

Переменные, значениями которых служат высказывания – это пропозициональные переменные. A — множество пропозициональных переменных. Поскольку значениями пропозициональных переменных являются высказывания, которые, в свою очередь, принимают значения либо И, либо Л, то и формула также принимает два значения — И либо Л.

Правильно построенными формулами (ППФ) являются формулы:

1) атомарная формула является ППФ (простейшая)

2) если A – ППФ, то и ~А – тоже ППФ

3) Если G и H – ППФ, то (GvH), (GᴧH), (G→H), (G<->H) – тоже ППФ

4) Никакие другие формулы, кроме формул порожденных правилами 1-3 не являются ППФ.

При записи формул можно обойтись без некоторых скобок, если учитывать ранги логических связок по порядку (от высшего к низшему): ~, ᴧ, v, -> , <->.

5.  Доказательство коммутативности и ассоциативности конъюнкции.

  – коммутативность конъюнкции;

Доказывается через таблицу истинности.

Таблица истинности – это таблица перечисления всех комбинаций истинности и ложности, а так же применение операции.

Два высказывания равны, если у них совпадают таблицы истинности.

 – ассоциативность конъюнкции;

1)

2)

6. Доказательство коммутативности и ассоциативности дизъюнкции.

 – коммутативность дизъюнкции;

Доказывается через таблицу истинности.

Таблица истинности – это таблица перечисления всех комбинаций истинности и ложности, а так же применение операции.

Два высказывания равны, если у них совпадают таблицы истинности.

 – ассоциативность дизъюнкции;

1)

2)

7. Доказательство дистрибутивности конъюнкции относительно дизъюнкции.

 – дистрибутивность конъюнкции относительно дизъюнкции;

Доказывается через таблицу истинности.

Таблица истинности – это таблица перечисления всех комбинаций истинности и ложности, а так же применение операции.

Два высказывания равны, если у них совпадают таблицы истинности.

1)

2)

8. Доказательство законов де Моргана для булевой алгебры.

Булева алгебра логики — это алгебра, состоящая из нулей и единиц; или истины (TRUE)и лжи (False). В программировании булева алгебра логики встречается очень часто.

 – второй закон Моргана.

9. Доказательство закона контрапозиции.

p→q = ~q → ~p

1)

2)

10. Доказательство дистрибутивности дизъюнкции относительно конъюнкции.

 – дистрибутивность дизъюнкции относительно конъюнкции.

11. Тавтология. Определение. Примеры.

Высказывание, истинное во всех случаях, называется логически истинным, или тавтологией. Теоремы в математике – примеры тавтологии. Высказывание «Он сдаст или не сдаст экзамен» тоже пример тавтологии, потому что одно из этих событий в любом случае справедливо. Каждое высказывание вида

p V ~p – тавтология.

Еще примеры:

Если сдаст, то сдаст. Если он богат и удачлив, то он удачлив.

12. Понятие доказательства. Определение правильного доказательства.

Доказательством называется цепочка логических умозаключений, показывающая, что при каком-то наборе аксиом и правил вывода верно некоторое утверждение. Доказательство – неотъемлемая часть проверки корректности алгоритма. Необходимость доказательства возникает, когда нужно установить истинность высказывания вида P -> Q. Существует несколько стандартных типов доказательств: прямое суждение, обратное суждение, метод от противного.

Простите ребят, больше ничего не нашла.

13. Доказательство правила отделения (modus ponens)

Логические правила, которые используются для вывода новых теорем из аксиом, постулатов и ранее доказанных в данной системе теорем, не порождают в качестве «теорем» ложные высказывания. Эти логические правила называются правилами вывода. Умозаключение состоит из совокупности утверждений, называемых гипотезами. Правильным умозаключением называется такое умозаключение, заключение которого истинно всякий раз, когда истинны гипотезы. Представляются умозаключения в виде

Три точки – «следовательно». Умозаключение правильно, если всякий раз, когда гипотезы истинны, то истинно и С, т. е. H1ᴧH2ᴧH3 истинно.

Это правильно умозаключение называется правилом отделения. Пример: предположим, b – челое число. Тогда пусть

p: b четное

q: b делится на 2,

так что

p -> q: если b четно, то b делится на 2.

По правилу отделения:

если b четное, то b делится на 2

b четное

то значит что b делится на 2

Проверить это можно с помощью таблицы истинности.

Когда истинны все посылки (только случай 1) истинным является и заключение, значит и само умозаключение является правильным.

14. Доказательство исключения исключения. Modus Tollens.

Логические правила, которые используются для вывода новых теорем из аксиом, постулатов и ранее доказанных в данной системе теорем, не порождают в качестве «теорем» ложные высказывания. Эти логические правила называются правилами вывода. Умозаключение состоит из совокупности утверждений, называемых гипотезами. Правильным умозаключением называется такое умозаключение, заключение которого истинно всякий раз, когда истинны гипотезы. Представляются умозаключения в виде

Три точки – «следовательно». Умозаключение правильно, если всякий раз, когда гипотезы истинны, то истинно и С, т. е. H1ᴧH2ᴧH3 истинно.

Это умозаключение называется исключением исключения.

Докажем через таблицу истинности

Когда истинны все посылки (только случай 4) истинным является и заключение, значит и само умозаключение является правильным.

15. Доказательство силлогизма.

Логические правила, которые используются для вывода новых теорем из аксиом, постулатов и ранее доказанных в данной системе теорем, не порождают в качестве «теорем» ложные высказывания. Эти логические правила называются правилами вывода. Умозаключение состоит из совокупности утверждений, называемых гипотезами. Правильным умозаключением называется такое умозаключение, заключение которого истинно всякий раз, когда истинны гипотезы. Представляются умозаключения в виде

Три точки – «следовательно». Умозаключение правильно, если всякий раз, когда гипотезы истинны, то истинно и С, т. е. H1ᴧH2ᴧH3 истинно.

Это силлогизм.

Докажем через таблицу истинности.

Когда истинны все посылки (в случаях 1 и 8) истинным является и заключение, значит и само умозаключение является правильным.