Главная страница

Логика предикатов кратко. Логика высказываний


Скачать 140,5 Kb.
НазваниеЛогика высказываний
АнкорЛогика предикатов кратко.doc
Дата13.01.2020
Размер140,5 Kb.
Формат файлаdoc
Имя файлаЛогика предикатов кратко.doc
ТипДокументы
#17250
страница1 из 4
  1   2   3   4

    1. Логика высказываний

      1. Высказывания


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

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

Например,

P: “Температура высокая.”

Q: “Влажность большая.”

R: “Будет дождь.”

Идентификаторы ( P, Q, R ), которые используются для обозначения высказываний, называются атомарными формулами.

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

Название

Обозначение

Другие обозначения

отрицание

*





not

не

конъюнкция



&*

,

and

и

дизъюнкция

*

|

;

or

или

импликация



*






если

эквивалентность



*



тогда и только тогда

*– эти обозначения далее в тексте приняты для логических операций.
      1. Формулы


Правильно построенные при помощи логических связок составные высказывания называются формулами.

Например, предложение “Будет дождь, если температура высокая и влажность большая” можно записать в виде следующей формулы ( P & R ) Q.

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

Формулы логики высказываний с использованием формализма Бэкуса-Наура (БНФ) имеют следующий синтаксис:

< формула > :: = И | Л |

< атомарная формула > |

( < формула > ) |

( < формула > & < формула > ) |

( < формула > < формула > ) |

( < формула > < формула > ) |

( < формула > < формула > )

Пусть P и Q некоторые атомарные формулы, для которых известны их логические значения, тогда функция истинности для логических связок может быть вычислена по таблице истинности:

P

Q

P

P & Q

P Q

P Q

P Q

false

false

true

false

false

true

true

false

true

true

false

true

true

false

true

false

false

false

true

false

false

true

true

false

true

true

true

true

Импликация – очень важная связка; она отражает структуру рассуждений. Первый её операнд называется посылкой, а второй – заключением. Ясно, что если посылка истинна, то импликация принимает значение истинности заключения. Однако может вызвать удивление, что импликация бывает истинна и тогда, когда её посылка ложна. Импликация является единственной связкой, удовлетворяющей следующим требованиям:

  1. Если первый операнд истинный, то значение истинности совпадает со значением второго операнда.

  2. Значение истинности зависит от двух операндов.

  3. Связка некоммутативна.

Последнее требование легко иллюстрируется примером из естественного языка со связкой «потому что». Например, справедливо высказывание «Земля мокрая, потому что идёт дождь», но нельзя считать истинным высказывание «Идёт дождь, потому что земля мокрая».
      1. Интерпретация


Интерпретировать формулу – значит приписать ей одно из двух значений истинности true или false.

Значение истинности формулы зависит:

  • от структуры этой формулы;

  • от значения истинности составляющих её высказываний.

Если формула содержит N различных высказываний, то она имеет 2N возможных интерпретаций.

Формула может быть истинна при одной интерпретации (она имеет значение true) и ложной (она принимает значение false) при другой интерпретации.

Формула, истинная при некоторой интерпретации, называется выполнимой. Например, A A ( формула истинна при A = false).

Формула, истинная при всех возможных интерпретациях, называется общезначимой (или тавтологией) и обозначается . Например, A A.

Формула, ложная при всех возможных интерпретациях, называется невыполнимой (или противоречием) и обозначается . Например, A & A.

Теорема.

Пусть А – некоторая формула. Тогда:

  1. если А – тавтология, то А – противоречие, и наоборот;

  2. если А – противоречие, то А тавтология, и наоборот;

  3. если А – тавтология, то неверно, что А – противоречие, но не наоборот;

  4. если А – противоречие, то неверно, что А – тавтология, но не наоборот.

Доказательство. Очевидно из определений.

Теорема.

Если формулы А и А В – тавтология, то формула В – тавтология.

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

Пусть I ( B ) = false. Но I ( A ) = true, так как A – тавтология.

Значит I ( А В ) = false, что противоречит предположению о том, что А В – тавтология.
      1. Логическое следствие и логическая эквивалентность


Пусть даны формулы F1, F2,…Fn и формула G. Говорят, что G является логическим следствием формул F1, F2,…Fn, если и только если для всякой интерпретации I, в которой формулы F1, F2,…Fn истинны, формула G также истинна.

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

Теорема.

( P Q ) ( P Q )

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

P

Q

P Q

P

P Q

false

false

true

true

true

false

true

true

true

true

true

false

false

false

false

true

true

true

false

true

Путём перебора всех возможных интерпретаций (построением таблиц истинности) могут быть доказаны эквивалентности следующих формул:

  1. P Q ( P Q ) & ( Q P )

  2. P Q P Q

  3. P Q Q P

P & Q Q & P

  1. ( P Q ) R P ( Q R )

( P & Q ) & R P & ( Q & R )

  1. P ( Q & R ) ( P Q ) & ( P R )

P & ( Q R ) ( P & Q ) ( P & R )

  1. P P

P & P

  1. P

P &

  1. P P   закон исключения третьего

P & P закон противоречия

  1. ( P ) P  закон двойного отрицания

  2. ( P Q ) P & Q  1-ый закон де Моргана

( P & Q ) P Q  2-ой закон де Моргана

      1. Конструктивное определение исчисления высказываний


Исчисление высказываний – это формальная теория, в которой:

  1. Алфавит:

и – связки;

( , ) – служебные символы;

a, b, …, a1, b1,… – атомарные формулы.

  1. Формулы:

переменные – суть формулы;

если A, B – формулы, то ( A ) и ( A B ) – формулы.

  1. Аксиомы – три конкретные формулы:

( a ( b a ) )

( ( a ( b c ) ) ( ( a b ) ( a c ) ) )

( ( b a ) ( ( b a ) b ) )

  1. Правила вывода:

Правило подстановки: если формула В является частным случаем формулы А, то В непосредственно выводима из А.

Правило modusponens: если набор формул А, В, С является частным случаем набора трёх конкретных формул a, a b, b, то формула С является непосредственно выводимой из формул А и В.
      1. Теорема о дедукции


Пусть даны формулы F1, F2,…Fn и формула G.

Тогда формула G является логическим следствием формул F1, F2,…Fn,

если и только если формула вида ( F1 & F2 … & Fn G ) является общезначимой

и наоборот.

Доказательство:

I.

Предположим, что G является логическим следствием формул F1, F2,…Fn.

Пусть I – произвольная интерпретация для F1, F2,…Fn.

Если все F1, F2,…Fn истинны в I, то по определению логического следствия G тоже истинна в I.

Тогда формула ( F1 & F2 … & Fn G ) истинна в I по определению операции импликации ( t t = t ).

С другой стороны, если не все F1, F2,…Fn истинны в I, то есть хотя бы одна из них ложна в I,

тогда формула ( F1 & F2 … & Fn G ) истинна в I по определению операции импликации ( f f = t или f t = t ).

Таким образом, формула ( F1 & F2 … & Fn G ) истинна для всякой интерпретации, то есть она является общезначимой.

II.

Пусть ( F1 & F2 … & Fn G ) – общезначимая формула.

Тогда для всякой интерпретации I, если формула F1 & F2 … & Fn истинна в I, то G должна быть истинна в I по определению операции импликации. То есть формула G является логическим следствием формул F1, F2,…Fn, что и требовалось доказать.
      1. Следствие


Формула G является логическим следствием формул F1, F2,…Fn, если и только если формула вида ( F1 & F2 … & Fn & G ) противоречива.

Доказательство:

По теореме о дедукции G является логическим следствием формул F1, F2,…Fn, если и только если формула ( F1 & F2 … & Fn G ) общезначима, то есть её отрицание противоречиво:

( F1 & F2 … & Fn G )

( ( F1 & F2 … & Fn ) G )

( ( F1 & F2 … & Fn ) ) & G

F1 & F2 … & Fn G

Что и требовалось доказать.
      1. Выводимость


Если существует правило вывода R, то говорят, что G непосредственно выводима из формул F1, F2, …Fn по правилу вывода R. Обычно этот факт записывают следующим образом:

F1, F2, …Fn

 R

G

Если формула G является логическим следствием формул F1, F2, …Fn,

то формула вида ( F1 & F2 … & Fn G ) называется теоремой,

формулы F1, F2, …Fn – посылками теоремы,

G – заключением теоремы.
      1. Выводы


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

Атомарная формула в логике высказываний рассматривается как единое целое, её структура никак не анализируется.

Логика высказываний – раздел логики, в котором вопрос об истинности или ложности высказываний решается на основе изучения способа построения высказываний из не разделяемых и не анализируемых высказываний с помощью логических операций конъюнкции, дизъюнкции, отрицания, импликации и эквивалентности.
    1.   1   2   3   4



написать администратору сайта