Лекции по Логика

ЛОГИКА

ПРОПОЗИЦИОНАЛННА ЛОГИКА
(СЪЖДИТЕЛНО СМЯТАНЕ – СС)

Обект на изучаване на СС са обектите и операциите с тях по някакво съждение се отнася към първичните понятия на формалната логика но не може да бъде определено само в нейните граници. С(съждението) е отражение на реалната действителност, то е форма на мислене, с която се отразява обективно връзката между обектите или понятията. Оразяването му става под формата на повествователно изречение на естествен говорим език. С е вярно (то е истина), ако адекватно отразява тази връзка и е невярно, тоест лъжа в противния случай. С се означават с p,q,s и т.н. Ако С р е вярно, то верностната стойност на р е равна на 1, а р е невярно, когато верностната му стойност е равна 0
Примери:

Числото 4 е четно! - е вярно съждение V=1
и т. н.

Всяко елементарно С има следната структура:
субект на С – се нарича още и логически подлог, представлява понятието, за което се твърди нещо в С. Означава се с S от лат. Субект.
предикат на С – се нарича още и логическо сказуемо, отразява определен признак, свойство или отношение на обектите. Означава се с P от лат. Предикат.
логическа връзка – начините на задаване на едно С, както и след това работата с него, са различни. Например:
1. Да се определи дали едно С е вярно или невярно.
2. Създават се предпоставки, за да се изкаже С – например задават се числата 20,15,2,3,6,18 и съответно релациите по-голямо, по-малко,+,-, и т.н и условието е с посочените числа и релации, посочете верни или неверни твърдения.
3. Изказват се фрази, задава се запис и се изисква да бъдет допълнени с думи, числа или знаци така, че да станат верни или неверни С. Например, за да бъде един правоъгълник квадрат (е достатъчно условие............), страните да са равни.

Видове С

Основно деление на С е делението им на прости(елементарни) и сложнни(съставни) С. Едно С е просто, когато от него не може да се отдели друго С.
Въз основа на съдържанието на Р, С се делят на С за свойства и С за отношения. Например: числото 4 е четно е С за свойство, за отношение е всяко едно от релациите.
Според това, каква част от обема на S се включва или не се включва в обемът на Р, С се делят на общи и частни. Общите С имат следната формула всяко S е Р или всички S са Р. Частните са някое S е Р и някои S са Р. Или не е и не са.
Според качеството на връзката между S и Р, С се делят на уттвърдителни и отрицателни. УС са с формулата S е/са P, а отрицателните са S не е/не са Р.
В зависимост от качеството на връзката и частта от обемът на S, която се включва или не в обемът на Р, С се делят на общо утвърдителни, частно утвърдителни, общо отрицателни и частно отрицателни. Например общо утвърдително е всички хора са смъртни; частнно утвърдително е някои небесни тела са звезди; общо отрицателни са всички болести не са белодробни; частно отрицателни са някои животни не са бозайници.

Операции със С

От простите и елементарни С, за които първоначално се знае, дали са исстина или лъжа, с помощта на логически операции наречени функтори Ф(конюнкция – съюз и, дизюнция – или, импликация - ако...то, еквиваленция – тогава и само тогава когато, отрицание – не). Това са 5-те операции на СС.

Определение - всяко съответствие от вида Vна Р, ако приема V=0 или 1, се нарича разпределение на верностните стойности на съждителните променливи (РВССП).

Определение – отрицанието на едно С е също С, което е вярно тогава и само тогава когато изходното С е невярно, тоест ако е зададено С р неговото отрицание е /р(не пе).

Определение – конюнкцията е „и“ , записва се рΛq, следователно конюнкцията е С съставено от две прости С. Една конюнкция приема верностна стойност 1, тогава и само тогава, когато и двете изходни С са верни. Верностната таблица(ВТ) е:

Определение – дизюнкция „или“, записва се pVq, чете се пе или кю. Твърдението е невярно само тогава, когато и двете са неверни. ВТ е:

Разделителна дезюнкция – pWq (чете се или пе или кю). Тоест твърдението е вярно тогава, когато едно от двете С са верни и невярно, тогава когато и двете са верни или неверни. Тогава ВТ е:

Импликация „ако..то..“ - означава се p →q. Импликацията е невярна само тогава когато изходното С е вярно, но второто е невярно. ВТ е следната:

Еквиваленция - „тогава и само тогава когато“ p ↔q, чете се тогава и само тогава когато кю. ВТ е:

ЗАДАЧИ:
Постройте ВТ на следната съждителна схема: дадени са p,q и r.
(pΛ/r)→{(qW/p)↔(/qVr)}

Например: въпрос за кои верностни стойности на цялата система е противоречие алфа =0,
V(p)=1
V(q)=1
V(r)=0 или
V(p)=1
V(q)=0
V(r)=0

Закони на СС

Определение тафталогия – Ссхема алфа се нарича тафталогия (├), тогава и само тогава, когато при всяко РВССП, верностната стойност на V(α)=1. Отрицанието на това определние гласи: една съждителна схема не е тафталогия, тогава и само тогава, когато съществува РВССП, при което тя приема ВС =0.
α е ├ <=>¥ РВССП V(α)= 1
α не е ├ <=> Э РВССП V(α)= 0

Противоречие – всяка С схема α, при която всяко РВССП верностната стойност е 0.
α е противоречие <=>¥ РВССП V(α)= 0

Две С схеми α и β са равнозначни, тогава и само тогава, когато еквиваленцията между двете схеми е тафталогия.
α ≈ β <=> α↔ β е ├

С схема α→ β, тогава и само тогава, когато имплликацията между двете е тафталогия.
α => β <=> α→ β е ├

Правила за доказване на СС

Операцията, която на схемите А1,А2, А3 и т.н.(предпоставки) съпоставя схема В(заключения), се нарича правило за доказване в СС - ПДСС, тогава и само тогава, когато при всяко РВССП, всички предпоставки А1,А2 и т.н. приемат верностна стойност 1-ца, то и заключението приема верностна стойност 1-ца . Това определение не е ПД тогава и само тогава, когато В приеме верностнна стойност 0. Ако всички предпоставки в дадено ПД са тафталогия, то и заключнието трябва да бъде тафталогия.
A1,A2,A3…An
B

Правила на условният силогизъм УС

Правила за доказване
Ако алфа импплицира бета и бета имплицира гама, то алфа имплицира гама.
α →β, β→γ
α→γ
Алфа имплицира бета, бета имплицира гама илплиира алфа имплицира гама.
α →β
(β→γ) →(α→γ)

Бета имплицира гама, алфа имплицира бета имплицира алфа имплицира гама.
β →γ
(α→β) →(α→γ)

Доказателство на 2. : За да бъде схема М ПД, тя трябва да е тафталогия, тоест
М=( α →β)→ {(β→γ)→(α→γ)} е├
Допускаме противното, тоест че съществува РВССП, за което верностна стойност на М е 0. Следва че верностната стойност на алфа импликация бета е 1-ца, а заключението има верностна стойност 0. Верностната стойност на бета импликация алфа трябва да бъде 1-ца, а на алфа импликация с гама да е 0, но от второто следва, че верностната стойност на алфа е 1 а на гама е 0, но от предищното твърдение следва че верностната стойност на бета е 0. Но при заместването виждаме, че твърдението е противоречие, следователно допускането е невярно, тоест няма РВССП при което верностната стойност на М е 0, следователно М е тафталогия следователно е ПД.
=> V(α→β)= 1 V(β→γ)=1 V(β)=0
V{(β→γ)→(α→γ)}=0 V(α→γ)=0 V(α)=1
V(γ)=0

От α=1 и β=0, следва че V(α→β)= 0, следователно има противоречие и допускането е невярно, тоест не съществява такова РВССП.

=> М е ├ => М е ПД

Правила за доказване с отделяне

Ако алфа и алфа в еквиваленция бета, то бета
α, α ↔β
β
Ако алфа и алфа в еквиваленция с бета, то бета
α, α ↔β и β, α ↔β
β β

Доказателство на 1: за да бъде тази схема А ПД, то А={α Λ(α↔ β)}→β е ├ ,
следователно V(A)=1 за ¥ РВССП.
Допускаме, че съществува РВССП, за което V(A)=0, но по определението за импликация
V{α Λ(α↔ β)}= 1
V(β)=0 =>

V(α)=1
V(α↔ β)= 1 => V(α↔ β)= 0 противоречие
V(β)=0

следва, че допускането е невярно, следователно схема А е тафталогия и е правило за доказване.

Правила за доказване с конюнкция и дезюнкция

с конюнкция
- α ,β
α Λ β

- α Λ β и α Λ β
α β
- α →β, γ →δ
(α Λγ) →( βΛγ)

- α →β, γ →δ
α→( βΛγ)

с дизюнкция
- α и β
αVβ αVβ

- α → γ ,β→ γ
(α Vγ) → γ

- α →β, γ →δ
(αVγ) →( β→δ)

- α V β, / α и α V β, / β
β α

Правила за опростяване

α
β→α

α→( β→γ) и α→( β→γ), α →β
(α→β)→ (α→ γ) α→ γ

/α
α→β

/α→ α
α

Закони на съждителното смятане

Комуникативни закони
//p↔p (закон на двойното отрицание)
(pΛp) ↔p и (pVp) ↔p ( закон на повторението)
(pΛq) ↔(qΛp) ; (pVq) ↔(qVp) ; (p↔q) ↔(q↔p)

Асоциативни данни
[(pΛq) Λr] ↔[pΛ(qΛr)] и [(pVq) Vr] ↔[pV(qVr)]
[pΛ(qVr)] ↔[(pΛq)V(pΛr)]

Дистрибутивен закон
[pV(q Λr] ↔ [(pVq) Λ(pVr)]

Закони на Де Морган
/(p Λq) ↔ (/pV/q)
/(p Vq) ↔ (/pΛ/q)

Закон за внасяне и изнасяне
[(p Λq) →r] ↔ [p→(q→r)]

(p→q) ↔ (/pVq)
(pVq) ↔(/p→q)

Закон за отрицание на импликацията
/(p→q) ↔ (pΛ/q)

(p↔q) ↔ [(p→q) Λ(q→p)]
/(p↔q) ↔ [/(p→q) V/(q→p)]
(p→q) ↔ (/q→/p)
[(pΛq)V/q] ↔(pV/q)

Доказателство на α =(p↔q) ↔ [(p→q) Λ(q→p)]

Доказателство на α =/(p→q) ↔ (pΛ/q)

ЗАДАЧА 1:
Да се провери дали конюнкцията на съответно представящите ги схеми не е контрадикция или противоречие.
Или свидетелят не е бил заплашен, или ако Георгиев е избягал, то писмото е било намерено.
Ако свидетелят е бил заплашен, то Георгиев не би избягал.
Ако писмото е било намерено, то Георгиев е избягал.
s – свидетелят не е заплашен
g – Георгиев е избягал
p – писмото е намерено
/s – свидетелят е заплашен
/g – Георгиев не е избягал
/p – писмото не е намерено

sW(g→p)
/s→/g
p→g
=> α =[sW(g→p)] Λ(/s→/g) Λ(p→g)

ЗАДАЧА 2:
След банков обир полицията привиква на разпит заподозрени от бандата на дебелооките – Картофа, Бирата и Рибата. Кратка стенограма от разпита на бандитите:
К.: Не съм аз и Бирата е невинен.
Б.: Картофа е чист, Рибата е виновен.
Р.: Нямам нищо общо, Картофа беше.

Оказало се, че само един от тях е казал истината, единият е излъгал, а третият е казал едно вярно и едно невярно съждение. Кой е извършил обира?

k – невинен /к - виновен
б – невинен /б - виновен
р – невинен /р – виновен

к Λб
к Λ/р
р Λ/k
=> α =( к Λб)W(к Λ/р)W(р Λ/k)

=> Картофа е невинен - виновни са Рибата и Бирата

ФУНКЦИОНАЛНА ЛОГИКА(ФЛ)
(ПРЕДИКАТНО СМЯТАНЕ-ПС)

ФЛ може да се охарактеризира, като връщане назад и задълбочаване на символната логика. Връщане защото непосредствено логическия мотив за разработката и е неспособността на СС да се справи с отдавна познати и изследвани умозаключителни форми.
Пример: Всички хора са смъртни. Сократ е човек, следователно Сократ е смъртен.

Първите символи, които срещаме във ФЛ са буквите f,g,p, с които означават функции, а с малките x,y,z се означават аргументите. С помощта на скоби функциите и аргументите се свързват и се образуват формули - f(x), g(x,y), p(x,y,z).
Всяко x p(x) наричаме квантор за всеобщност (означава се ¥ х), а съществува х (Эх) е квантор за съществуване, които свързват променливата х в логическа операция, тоест в този раздел на логиката (предикатната), ние ще изучим правилната употреба на кванторите, като логически операции. Кванторът за всеобщност може да се разглежда, като обощение на конюнкцията, тоест то е равносилно на следния запис:
¥ Р(xi) ≈ P(x1) V P(x2) V ...P(xn); i=n

Э P(xi) ≈ P(x1) V P(x2) V ...P(xn); i=n

Д – квантор за сила

¥ Р(x) ≈ Э P(x)
Д

Употребата на кванторите в област Д, може да има и по-сложен характер. Често се използват следните изрази, като всяко х от Д удовлетворява условие q и притежава свойство р.

х э Д х е Д
¥ хР(x) Э хP(x)
Q(x) Q(x)

¥ хР(x) ≈ ¥ х [Q(x) →P(x)]
Q(x)

Э хР(x) ≈ Э х [Q(x) Λ P(x)]
Q(x)

Интерпретация. Модел

Определение: Под интерпретация(И) ще разбираме всяка система състояща се от непразно множество”Д”, което ще наричаме област на интерпретацията. И съответствие представящо на всяка предикатна буква някаква релация, на всяка функционална буква някаква операция, а на всяка предметна константа някакъв елемент от „Д”.

Определение: Формула „А” е изпълнена тогава и само тогава, когато се получава вярно в дадената интерпретация твърдение.

Определение: Формула „А” се нарича истинна в дадена интерпретация тогава и сам тогава, когато тя е изпълнена за всяка редица „Д”.

Определение: Формула „А” се нарича противоречива в дадена интерпретация тогава и само тогава, когато тя не е изпълнена за никоя редица „Д”.

Определение: Една интерпрета