Логика высказываний. F1: Если жарко и сыро, то будет дождь

F₁: Если жарко и сыро, то будет дождь.

F₂: Если сыро, то жарко.

F₃: Сейчас сыро.

P – жарко

Q - сыро

R – будет дождь

F₁: P Q R F_n: R

F₂: Q R Вытекает из житейской логики если считать, что F_1, F_2, F₃ имеют место.

F₃: Q

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

истина “1” ложь “0”

Пример:

сахар белый.

сахар углеводород.

Глекоров имеет степень доктора наук.

P, Q, R – атомарные формулы – атомы.

Логические связки: “и” -

“или” -

“если…то” -

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

“не” -

Приоритеты связок

G	H	G	G H	G H	G H	G H	H

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

(P Q) (R S)

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

	P	Q	R	S	S	P Q	R S	P Q R S

Обще значимость и противоречивость.

Формула истиностная на всех интерпретациях – обще значимая формула (тавтология)

╞A – A обще значима.

P	Q	P Q	(P Q) P	((P Q) P) Q	((P Q) P) Q)

((P Q) P) Q и (((P Q) P) Q)

определение.

FA возможно эквивалентна всех интерпретаций А истина (FA)<=>A обще значима.

Формула противоречива (невыполнима) тогда и только тогда когда она ложна во всех возможных интерпретациях.

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

1. ╞A<=> А – невыполнимо

2. А невыполнима <=>╞ A

3. ╞A<=>существует интерпретация когда она ложна

4. А выполнима <=> существует интерпретация когда она истина

5. ╞A=> непротиворечива

6. А невыполнима => ╞A.

Конъюнктивная нормальная форма.

F₁ … F_n где F₁,…,F_n – дизъюнкции литер.

Дизъюнктивная нормальная форма.

F₁ … F_n F₁,…,F_n - конъюнкции литер.

Определение.

] F₁,…,F_n и формула G.G есть логическое следствие F₁,…,F_n (выводима из них) тогда и только тогда когда все интерпретации I, в которой F₁ … F_n истина G также истина

F₁,…,F_n - аксиомы (поступаты, посылки) G F₁,…,F_{n ├} G

Теорема 2.

P	Q	P Q	¯|Q	P Q ¯|Q	P Q Q P

(P Q) Q ((P))=P Q Q P

(P Q) Q P= P Q P Q Q P=0 0=0

Пример стр. 5а

Дата добавления: 2015-06-27