uzluga.ru
добавить свой файл


Исчисление высказываний


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

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

    • x: “земля круглая”,
    • y4: “плотность воды составляет 0.5т/м3”,
    • z: “идет дождь”.


Построение формальных теорий

  • Выбирается алфавит теории, т. е совокупность разрешимых символов.

  • Указывается правило составления «правильных» выражений – формул.

  • Из множества формул делается выделение формулы или аксиомы.

  • Указываются правила вывода, т. е правила получения теорем.



Пропозициональная переменная  и формула

  • Пропозициональная переменная — переменная, значением которой может быть логическое высказывание.

    • Если P — пропозициональная переменная, то P — формула.
    • Если A — формула, то ¬А — формула.
    • Если A и B — формулы, то (A→B), (A∨B) и (AB) — формулы.
    • Других соглашений нет.
  • Знаки ¬, →, ∨ и  (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками



Классификация формул

  • Формула называется выполнимой, если существует конкретный набор высказываний, при подстановке которого в формулу получается истинное высказывание.

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

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

  • Формула называется тождественно-ложной или противоречивой, если она на любом наборе высказываний представляет собой ложное высказывание, при любом а.



Аксиомы ФИВ



Правила вывода



Теоремы

  • AA, AA (закон двойного отрицания)

  • A(AB) (из ложного, что угодно)

  • (BA)(AB), (AB)(BA) (закон противоположности)

  • A(B (A B))



Предикат

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



Предикаты

  • Местностью предиката называется количество различных предикатных переменных, входящих в предикат.

  • Одноместный предикат - x впадает в Каспийское море

  • Двухместный предикат - x впадает в y.



Классификация предикатов

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

  • Предикат называется опровержимым, если существует хотя бы один набор предметных переменных, при которых он превращается в ложное высказывание.

  • Тождественно истинным называется предикат, если для любого набора предикатных переменных он является истинным высказыванием.

  • Тождественно ложным называется предикат, если для любого набора предикатных переменных он является ложным высказыванием.



Множество истинности

  • Множество истинности P+ предиката P(x), определенного на базовом множестве M (xM), называется множество тех элементов xM, для которых P(x) истинно.



Равносильность и следствие



Теоремы

  • Пусть из P ⇒ Q, т.е. Q следствие P, тогда если P – тождественно-истинно (выполнимо), то и Q – тождественно-истинно (выполнимо).

  • Если Q – тождественно-ложный (опровержимый) предикат, то и P – тождественно-ложный (опровержимый) предикат.



Кванторы

  • Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката.

  • Квантор всеобщности (обозначение:  ∀, читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).

  • Квантор существования (обозначение: ∃, читается: «существует…» или «найдётся…»).



Квантификация

  • ∀x P(x)

  • ∃x P(x)

  • ∀x ∃y P(x,y,z)