Презентация на тему "Логика высказываний"

Содержание

• 
  Слайд 1
  

  Логика высказываний. Логические связки. Формулы алгебры высказываний. Тождественно-истинные формулы. Равносильность формул. Логическое следование. нормальные формы формул

• 
  Слайд 2

  НАПРАВЛЕНИЯ МАТЛОГИКИ

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

• 
  Слайд 3

  1. Предмет логики высказываний

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

• 
  Слайд 4

  2. Действия и операции над высказываниями.

  Пусть А и В – атомарные (пропозициональные) высказывания, тогда из них можно построить составные высказывания, используя логические связки. В математической логике используют пять логических связок:

• 
  Слайд 5

  3. Понятие пропозициональной формулы

  Определение. Алфавитом называется произвольное непустое множество. Элементы алфавита – символы. Определение. Слово – произвольная последовательность символов (возможно пустая). Определение. Произведением слов А и Вв некотором алфавите называется слово АВ. Определение. Слово В называется подсловом слова А, если существуют такие слова А1 и А2, такие что А=А1 В А2 Определение. Говорят, что слово С получено из слова А подстановкой слова D вместо подслова В, если А=А1 В А2 и С=А1 D A2 . Определение. Говорят, что слово С получено из слова А путем замены символа v на слово B, если в слове вместо всех символов v подставлено слово B.

• 
  Слайд 6
  

  Пусть имеется некоторое множество элементов, называемое алфавитом логики высказываний. Элементы этого множества можно разбить на следующие 3 группы:

  именные символы логические символы служебные символы P, Q, P1, Q1, ,,,,~. открывающиеся ( и закрывающиеся ) скобки Определение. Формулой алгебры высказываний называется: 1. Высказывательная (пропозициональная) переменная 2. Если и некоторые формулы, то тоже являются формулами. 3. Других формул, кроме перечисленных в пунктах (1) и (2), нет.  

• 
  Слайд 7

  4. Тавтологии и противоречия

  Пусть A(Х1,…,Хn) – пропозициональная формула, Х1,…,Хn - высказывательные переменные, входящие в формулу A. Определение. Интерпретацией формулы A называется любой конкретный набор истинностных значений, приписанных переменным Х1,…,Хn. Пусть I – некоторая интерпретация (т.е. набор значений переменных Х1,…,Хn). Тогда через I(A) обозначается значение формулы A в интерпретации I. Формулами, имеющими наиболее простую интерпретацию, являются формулы, равные И либо Л при любой интерпретации. Определение. Формула называется выполнимой, если она истинна хотя бы при одной интерпретации. Определение. Формула, истинная при всех возможных интерпретациях, называется общезначимой или тавтологией. Определение. Формула, ложная при всех возможных интерпретациях, называется невыполнимой или противоречием. Определение.Формула называется опровержимой, если при некоторой интерпретации она принимает значение Л.

• 
  Слайд 8
  
• 
  Слайд 9

  5. Основные правила получения тавтологий

  1 правило. Правило замены позволяет выполнять равносильные преобразования формул для их упрощения или приведения к специальной форме. Например для доказательства того, что формула является тавтологией нужно равносильными преобразованиями свести ее к формуле, очевидно являющейся тавтологией. Правило замены: если F(A1, A2, ... , An) = G(A1, A2, ... , An), то для любой формулы алгебры высказываний H(X1, X2, ... , Xi-1, Xi, Xi+1, ... , Xm) имеет место равносильность H(X1, X2, ... , Xi-1, F(A1, A2, ... , An), Xi+1, ... , Xm) = H(X1, X2, ... , Xi-1, G(A1, A2, ... , An), Xi+1, ... , Xm)   2 правило. Правило заключения основано на применении теоремы 1.2. Теорема 1.2: Если формулы A и AB – тавтологии, то B – тавтология. Доказательство: Предположим противное, т.е. для некоторой интерпретации I имеем I(B)=Л. I(A)=И, т.к. A – тавтология, то I(AB)=Л, что противоречит тому, что AB – тавтология.   3 правило. Правило подстановки: если формула F, содержащая атом A, является тавтологией, то подстановка в формулу F вместо A любой формулы H снова приведет к тавтологии.

• 
  Слайд 10

  6. Равносильность формул. Логическое следование.

  Определение. Две формулы A и B, зависящие от одного и того же набора высказывательных переменных называются равносильными, если I(A)=I(B) для любой интерпретации I. Равносильность формул A и B записывается следующим образом:AB. Определение. Формула B логически следует из формулы A (обозначается AB), если формула B имеет значение И при всех интерпретациях, при которых формула A имеет значение И. Отношение равносильности на множестве формул логики высказываний является отношением эквивалентности, так как оно: Рефлексивно AA Симметрично AB  ВА Транзитивно AB и ВС  АС

• 
  Слайд 11
  
• 
  Слайд 12
  

  докажем второй закон де Моргана на основе рассмотрения вариантов значений

  Пусть для некоторой интерпретации I имеем: I((AB))=ИI(AB)=Л I(A)=Л и I(B)=Л I(A)=И и I(B)=И I(AB)=И. Случай I((AB))=Л рассматривается аналогично. Обратно, пусть I(AB)=И I(A)=И и I(B)=И I(A)=Л, I(B)=Л I(AB)=Л I((AB))=И.

• 
  Слайд 13
  

  вопрос сохранения свойства равносильности формул при различных преобразованиях.

  Теорема 1.3. Пусть AB и C – произвольная формула. Тогда: A=B AC=BC; CA=CB AC=BC; CA=CB ACBC; CACB A~CB~C; C~AC~B Доказательство: продемонстрируем на примере одного из соотношений. Пусть при некоторой интерпретации I имеем I(A)=I(B)=s; и пусть I(C)=t. Тогда обе части каждой из формул, например, 4) ACBC принимают абсолютно одинаковый вид (st). 

• 
  Слайд 14
  

  Теорема 1.4. 1)Две формулы логики высказываний А и В равносильны тогда и только тогда когда формула A~B является тавтологией. 2)Формула В логически следует из А тогда и только тогда, когда АВ– тавтология. Следствие: AB AB – противоречие. Доказательство. 2) Необходимость: Пусть I(A)= И. Тогда из определения следования вытекает I(B)=И  I(AB)=И. Таким образом формула AB тавтология. Достаточность: Пусть AB – тавтология. Тогда для всякой I, такой что I(A)=И необходимо I(B)=И, иначе I(AB)=Л. Что означает, что A является логическим следствием B.

• 
  Слайд 15

  7. Нормальные формы формул логики высказываний.

  Элиминировать импликацию и эквиваленцию можно с использованием правила замены и равносильностей (AB)~( AB) и A~B(AB)(BA). Пронести отрицания можно с помощью снятия двойного отрицания и законов де Моргана Определение. Литера есть атом или отрицание атома. Определение. Формула А находится в конъюнктивной нормальной форме тогда и только тогда, когда она имеет вид A= A1  A2  …  AN, где каждая Ai есть дизъюнкция литер. Определение. Формула А находится в дизъюнктивной нормальной форме тогда и только тогда, когда она имеет вид A= A1 A2 … AN, где каждая Ai есть конъюнкция литер.

• 
  Слайд 16
  

  Теорема 1.5. Для любой формулы логики высказываний существует эквивалентная ей формула, находящаяся в КНФ. Теорема 1.6. Для любой формулы логики высказываний существует эквивалентная ей формула, находящаяся в ДНФ. Теорема 1.7. Для любой опровержимой формулы логики высказываний существует эквивалентная ей формула, находящаяся в СКНФ. Теорема 1.8. Для любой выполнимой формулы логики высказываний существует эквивалентная ей формула, находящаяся в СДНФ.