rachunek kwantyfikatorów

rachunek kwantyfikatorów

rachunek predykatów/logika pierwszego rzędu

* opisuje właściwości zdań prostych
* własności obiektów
* relacje między nimi
* zawiera się w nim rachunek zdań
* kwantyfikacja

operatory

wyrażenia, które po dodaniu ich do funkcji tworzą:

**stałe**

^^nazwowe^^ - operator nazwotwórczy

^^zdaniowe^^ - operator zdaniotwórczy

kwantyfikatory są operatorami zdaniotwórczymi

konkretyzacja - podstawienie za zmienną nazwy albo zdania - powstaje stała

x jest studentem - funkcja

Adam jest studentem - stała zdaniowa/zdanie

**funkcje o mniejszej liczbie zmiennych wolnych**

x jest studentem - %%funkcja%%

%%dodajemy kwantyfikator mały%%

istnieje x taki, że x jest studentem

%%to wyrażenie oznacza, że%%

istnieją studenci

%%nie ma już zmiennych - mamy zdanie%%

kwantyfikacja - podstawianie za zmienną kwantyfikatora

x jest ojcem y - funkcja - 2 zmienne wolne

dodajemy kwantyfikator mały

istnieje taki x, że x jest ojcem y

istnieje ojciec y - funkcja, 1 zmienna wolna

stałe logiczne

spójniki logiczne

* funktory zdaniotwórcze o argumentach zdaniowych


* takie same jak w rachunku zdań

kwantyfikatory

stałe nazwowe

nazwy jednostkowe, indywidualne - mają tylko jeden konkretny desygnat

**małe litery alfabetu**, odpowiadające nazwom w zdaniach

Michał - m

Warszawa - w

%%nie używamy nazw ogólnych!%%

zmienne nazwowe

do użycia w funkcjach

x, y, z

zakres zmiennej

to, co można podstawić za zmienną

najlepiej, żeby zakres był taki sam dla wszystkich zmiennych w funkcji

uniwersum

zbiór wszystkich tych rzeczy, które można podstawić za zmienną

zmienne a kwantyfikatory

\
**zmienna objęta kwantyfikatorem/wskaźnik**

* zmienna pod kwantyfikatorem - w zapisie
* zmienna, której dotyczy kwantyfikator

**zasięg kwantyfikatora**

* wyrażenie po kwantyfikatorze
* wyrażenie, w którym jest kwantyfikator

**zakres kwantyfikatora**

* zakres zmiennej, której dotyczy kwantyfikator

**zmienna związana**

* %%objęta%% + %%w zasięgu%%
* znajduje się w wyrażeniu z kwantyfikatorem
* dotyczy jej ten kwantyfikator

\

litery funkcyjne - dla nazw

oznaczają funktory nazwotwórcze o arg. nazwowych

**t2/1**

2 - górna cyfra - liczba argumentów

1 - dolna cyfra - liczba porządkowa

%%zawsze zapisywane małymi literami%%

litery dowolne, pasujące do elementów zdania

biały - b

dziecko - d

litery predykatowe - dla predykatów

oznaczają funktory zdaniotwórcze o arg. zdaniowych

**p2/1**

2 - górna cyfra - liczba argumentów

1 - dolna cyfra - liczba porządkowa

%%zawsze zapisywane dużymi literami%%

litery dowolne, pasujące do elementów zdania

kupuje - K

przenosi - P

kwantyfikatory

wyrażenia określające liczbę obiektów danego typu

**kwantyfikator uniwersalny/duży ∀**

%%właściwość dotyczy wszystkich elementów zbioru%%

odpowiednik koniunkcji - wszystkie elementy muszą mieć coś

* dla każdego
* dla dowolnego
* dla wszystkich
* każdy
* wszystkie

**kwantyfikator egzystencjalny/mały ∃**

%%właściwość dotyczy co najmniej jednego elementu albo wszystkich%%

odpowiednik alternatywy - conajmniej jeden obiekt musi mieć coś, ale mogą wszystkie

==**jeśli niektóre obiekty mają jakąś właściwość, to nie znaczy to automatycznie, że są obiekty które jej nie mają**==

* dla pewnego
* dla niektórych
* istnieje x taki, że..
* *czyimś*
* ktoś
* coś

zapis predykatu i argumentów

**zdanie**

^^Adam^^ ==kocha== ^^Ewę^^

^^Adam^^ - nazwa - a

==kocha== - predykat - K

^^Ewę^^ - nazwa - e

**K(a,e)**

kolejność argumentów taka jak w zdaniu

**funkcja**

x kocha y

**K(x,y)**

predykaty - złożone przyimki i negacja

**złożone przyimki**

Poznań ==leży między== Warszawą ==a== Berlinem

leży między - w logice jest jednym predykatem - M

Poznań - p

Warszawa - w

Berlin - b

M(p,w,b)

**negacja**

Nieprawda, że Ewa jest kobietą

Nieprawda,że - w logice to wskaźnik negacji, __nie predykat__

Ewa - nazwa - e

jest kobietą - w logice całość jest predykatem, bo “kobieta” to nazwa ogólna - K

\~K(e)

predykaty - zdania złożone

**implikacja**

$Jeśli$ Adam lubi Ewę, $to$ ją poślubi

Adam - nazwa - a

Ewa - nazwa - e

lubi - predykat - L

poślubi - predykat - P

L(a,e)→P(a,e)

* zaznaczamy implikację między zdaniami


* w drugim zdaniu jest elipsa, ale musimy przepisać argumenty, które zostały pominięte

**zdanie względne**

Ewa jest kobietą, $która$ mieszka w Poznaniu

która - zdanie względne oznaczamy koniunkcją

Ewa - nazwa - e

jest kobieta - predykat - K

mieszka - predykat - M

Poznań - nazwa - p

K(e)^M(e,p)

w drugim zdaniu jest elipsa, ale musimy przepisać argument, który został pominięty

deskrypcje

* nazwa złożona, która opisuje jeden desygnat
* grupa nominalna która opisuje tylko jedną rzecz

%%tylko jeden desygnat może być fizycznie możliwy%%

%%brat Marty - nie może być, bo braci może być wielu%%

**zapis nawiasowy** - metoda na cebulę

łysy kot (sąsiadki (babci))

k(s(b))

* małymi literami
* nawiasy okrągłe

∀x ∀y P(x,y)

Każdy obiekt typu x jest w relacji z każdym obiektem typu y

również ze samym sobą

∃x ∃y P(x,y)

istnieje conajmniej jeden obiekt x i obiekt y, które są ze sobą w relacji

\~∃x ∃y P(x,y)

nie istnieje obiekt x który jest w relacji z obiektem y

nikt nie jest w relacji z nikim

nikt nie jest niczyim znajomym

∀x ∃y P(x,y)

każdy obiekt x jest w relacji z conajmniej jednym obiektem y

∃x ∀y P(x,y)

conajmniej jeden obiekt x jest w relacji ze wszystkimi obiektami y

\~∃x ∀y P(x,y)

żaden obiekt x nie jest w relacji ze wszystkim obiektami y

nikt nie jest w relacji ze wszystkimi

nikt nie jest znajomym wszystkich

∀x B(x)

wszystkie elementy x z uniwersum mają właściwość B

*Wszyscy są blondynami*

∃x B(x)

conajmniej jeden obiekt x z uniwersum posiada właściwość B

*Niektórzy są blondynami*

\~∀x B(x)

Nie wszystkie obiekty x z uniwersum posiadają właściwość B, ale niektóre tak

*Nie każdy jest blondynem*

negacja dotyczy całego wyrażenia skwantyfikowanego

∀x\~B(x)

wszystkie obiekty x z uniwersum nie posiadają właściwości B

*Żaden nie jest blondynem*

^^żaden^^ - odpowiednik “każdy” używany w kontekście z negacją

negacja dotyczy tylko predykatu

\~∃x B(x)

nie ma w uniwersum takich obiektów x, które posiadają właściwość B

*Nikt nie jest blondynem*

*Nie ma blondynów*

*Nie istnieją blondyni*

^^nikt^^ - odpwiednik “niektórzy” używany w kontekstach z negacją

∃x\~ B(x)

istnieją takie obiekty x, które nie posiadają właściwości B

*Istnieją tacy, którzy nie są blondynami*

negacja dotyczy tylko predykatu

negacje w języku naturalnym

**∀x~B(x)** - ^^żaden^^

definicja wsjp

używane dla zaznaczenia, że wśród obiektów nazwanych następującym rzeczownikiem %%nie istnieje taki, którego dotyczy to, co zostaje powiedziane%%

**cała grupa nie posiada cechy**

**~∃x B(x)** - ^^nikt^^

definicja wsjp

informuje o tym, że %%nie ma kogoś takiego, o kim można by powiedzieć to, o czym mowa%%

etymologia

%%Forma prasłowiańska od zaimka \*kъto 'kto' z zaprzeczeniem \*ni-%%

\**związek z formą kto, czyli współczesne znaczenie ‘ktoś’ - wykładnik ∃*

tożsamości semantyczne

**~∀x B(x)** = **∃x~ B(x)**

Nie każdy jest blondynem **=** Istnieją tacy, którzy nie są blondynami

**∀x~B(x)** = **~∃x B(x)**

żaden nie jest blondynem **=** nikt nie jest blondynem

zamiana kolejności argumentów przy orzeczeniu imiennym

^^orzeczenie proste^^

**Z(x,y)** - x zna y, ==ktoś== zna $kogoś$, Marek zna Tomka

**∀x∃y Z(x, y)** - każdy zna kogoś

**∀y∃x Z(x, y)** - każdy jest czyimś rodzicem

==Marek== jest rodzicem $Kuby$

^^orzeczenie imienne^^

**Z(y,x)** - y jest znajomym x, $ktoś$ jest znajomym ==kogoś==, Tomek jest znajomym Marka

**∀y∃x Z(y, x)** - każdy jest znajomym kogoś

**∀y∃x R(y, x)** - każdy ma rodzica -

$Kuba$ ma rodzica ==Marka==

odwracamy kolejność zmiennych, bo obiekt będący rodzicem to x, a tutaj znajduje się on na końcu

tylko - semantyka

definicja wsjp

nadawca mówi, że %%to, co jest prawdziwe%% $o tym, o czym mowa$, nie jest prawdziwe o niczym innym

przykład

tylko $zwierzęta$ %%potrafią latać%%

%%to, co jest prawdziwe%% - potrafią latać L(x)

$o tym, o czym mowa$ - zwierzęta Z(x)

zamiana kolejności

wszystko to, co potrafi latać, jest zwierzęciem

**∀x[L(x)→Z(x)]**

^^nie możemy zachować kolejności z lewej do prawej, bo wtedy dostaniemy:^^

^^wszystkie zwierzęta potrafią latać^^

**w bardziej złożonych zdaniach**

%%I*rena nie lubi*%% *tylko* $*swoich sąsiadów*$

**zamienić na wersję prostszą**

$*tylko sąsiedzi Ireny*$%%*nie są lubiani przez Irenę*%%

i w zapisie odwrócić kolejność tak jak przy wersji prostej

nie tylko - semantyka

formuła taka sama jak przy tylko, ale z negacją

\~∀x\[L(x)→Z(x)\]

nie tylko zwierzęta potrafią latać

∃ z dwoma predykatami

∃x\[M(x)∧K(x)\]

*Niektóre mandarynki są kwaśne*

niektóre obiekty w uniwersum są mandarynkami i są kwaśne

∀ z dwoma predykatami

**∀x[C(x)→K(x)]**

*cytryny są kwaśne*

jeśli obiekt w uniwersum jest cytryną, to jest kwaśny

^^nie może być z koniunkcją, bo:^^

^^∀x\[C(x)∧K(x)\]^^

^^będzie oznaczało^^

^^wszystkie obiekty w uniwersum są cytrynami i są kwaśne^^

**negacja**

**∀x[P(x)→~L(x)]**

Żaden pingwin nie potrafi latać

==żaden ktoś nie jest coś = każdy ktoś nie jest coś==

Pingwiny istnieją, ale nie posiadają cechy latania

zdania składowe z kwantyfikatorami

**każdy kwantyfikator ma swój wyraz**

*Niektórzy* ==*studenci*== *przeczytali tylko* ==*książki*==

*Pewną* ==*książkę*== *przeczytali wszyscy* ==*studenci*==

**dalsza część zdania jest “opisem” konkretnego elementu na początku - tutaj** ==**studentów**== **i** ==**książki**==

**kwantyfikator z początku dotyczy całego zdania**

*Niektórzy…*

*Pewną…*

**cały schemat**


1. **∃x[S(x)∧∀y[P(x,y)→K(y)]]**
2. **∃x[K(x)∧∀y[S(x)→P(y,x)]]**

schemat - kolejność

poszczególne predykaty w schemacie złożonym opisujemy w kolejności SOV

**subject** - grupa podmiotu

**object** - grupa orzeczenia

**verb** - predykat czasownikowy albo przyimkowy

rozpisywanie schematu - procedura

*Irena nie lubi tylko swoich sąsiadów*


1. **szukamy kwantyfikatorów**

* ile ich jest?
* w czym się przejawiają

%%wyraz tylko%%

* czego dotyczą?

%%całego zdania%%

* Jaki to kwantyfikator?

%%∀%%

**szukamy stałych**

* co w tym zdaniu jest nazwą jednostkową?

%%Irena%%

**szukamy zmiennych**

* ile mamy w zdaniu “cosiów”?
* gdzie można stworzyć konstrukcje typu:
* coś jest czymś/kimś

%%coś jest sąsiadem%%

%%coś jest kimś, kogo Irena nie lubi%%

* sprawdzamy, czy te “cosie” dotyczą tej samej rzeczy czy nie - ile mamy zmiennych

%%tak, dotyczą%%

**szukamy predykatów - czasowniki i przyimki**

* sprawdzamy ilumiejscowy jest predykat

%%ktoś lubi kogoś%%

**szukamy predykatów - nazwy ogólne**

%%coś jest sąsiadem Ireny%%

%%nie lubi Irena kogoś%%

**sprawdzamy, czy nie mamy gdzieś elipsy - czy oczywiste elementy z początku zdania nie zostały pominięte w kontynuacji**

%%swoich=Ireny%%

**układamy predykaty**

%%\~L(i, x) - Irena nie lubi czegoś%%

%%S(x, i) - coś jest sąsiadem i jest Ireny%%


1. **układamy całość**

%%∀\[\~L(i, x)→S(x, i)\]%%

zasada kompozycyjności

składanie znaczenia globalnego ze znaczeń komponentów

znaczenie wyrażenia złożonego jest funkcją znaczeń jego składników

interpretacja

to, w jaki sposób wyrażenie odnosi się do rzeczywistości

zawiera

* uniwersum - czym są obiekty podstawiane za zmienne
* określone obiekty - co oznaczają stałe
* relacje i właściwości - co oznaczają predykaty

rozpisywanie interpretacji

Q(e)∧∀\[P(x)→Q(x)\]

*e ma własność Q i wszystkie wartości P mają też wartość Q*

U - uniwersum - zbiór ludzi

e - Ewa

P - bycie matką

Q - bycie kobietą

%%*Ewa jest kobietą i wszystkie matki są kobietami*%%

model

interpretacja, dla której wyrażenie jest prawdziwe

∃xP(x)

*istnieją obiekty o własności P*

U - zbiór ludzi

P - jest pilotem

%%Niektórzy ludzie są pilotami%%

kontrmodel

interpretacja, dla której wyrażenie jest fałszywe

∃xP(x)

*istnieją obiekty o własności P*

U - zbiór ludzi

P - jest ptakiem

==Niektórzy ludzie są ptakami==

Prawdziwość zdania egzystencjalnego - ∃

jest prawdziwe, jeśli można podać przykład spełniający warunki z interpretacji

fałszywość zdania uniwersalnego - \~∀

jest fałszywe, jeśli można podać przykład **niespełniający** warunków z interpretacji

Tautologie w rachunku kwantyfikatorów

**tautologia** - wyrażenie prawdziwe przy każdej interpretacji - nie ma dla niej kontrmodelu

**kontrtautologia** - wyrażenie fałszywe przy każdej interpretacji - nie ma dla niej modelu

pojęcie prawdy

funkcja zdaniowa jest prawdziwa, kiedy spełnia ją każdy obiekt z uniwersum

staje się zdaniem prawdziwym, gdy za wszystkie zmienne wolne wstawimy ∀

dictum de omni

∀xP(x)→P(x)

prawo opuszczania kwantyfikatora duzego

jak wszystkie zmienne z uniwersum maja dana wlasnosc, to kazda dowolna zmienna z tego samego uniwersum tez ma ta wlasnosc

dictum de singulo

P(x)→∃xP(x)

prawo dolaczania kwantyfikatora malego

jesli jakis obiekt ma wlasnosc P, to w tym samym uniwersum istnieja inne obiekty tez o wlasnosci P

jesli cos pojawilo sie raz, to znaczy, ze to istnieje

prawo subalternacji

∀xP(x)→∃xP(x)

zastepowanie duzego przez maly

jak wszystkie obiekty maja wlasnosc P, to znaczy ze istnieja obiekty o wlasnosci P

dictum de nullo

∀x\~P(x)→∃x\~P(x)

jak zaden obiekt nie ma wlasnosci P, to istnieja obiekty bez wlasnosci P

prawo przemianowywania zmiennych zwiazanych

∀xP(x)

prawa de Morgana

\~∃xP(x)

prawo zastepowania kwantyfikatorow

∃xP(x)

prawo przestawiania dużych i małych kwantyfikatorów

∀x∀yR(x,y)

prawo przestawiania malego za duzy

∃x∀yP(x,y)→∀y∃xP(x,y)

maly+duzy mozna zamienic na duzy+maly

**nie dziala w druga strone!!**

prawo rozdzielności dużego względem koniunkcji

∀x\[P(x)∧Q(x)\]

prawo rozdzielności małego względem alternatywy

∃x\[P(x)vQ(x)\]

prawo wyciągania dużego przed alternatywę

∀xP(x)v∀xQ(x)→∀x\[P(x)vQ(x)\]

jeśli wszystkie obiekty mają własność P lub mają własność Q, to wszystkie mają własność P lub Q

rozkładanie małego względem koniunkcji

∃x\[P(x)∧Q(x)\]→∃xP(x)∧∃Q(x)

jeśli obiekt ma własność P i Q jednocześnie, to ten obiekt ma własność P i ma własność Q

rozkładanie dużego względem implikacji

∀x\[P(x)→Q(x)\]→\[∀xP(x)→∀xQ(x)\]

jeśli wszystkie obiekty o własności P mają własność Q, to jeśli wszystkie obiekty mają własność P, to wszystkie te obiekty mają własność Q

rozkładanie małego względem implikacji

∀x\[P(x)→Q(x)\]→\[∃xP(x)→∃xQ(x)\]

jeśli wszystkie obiekty o własności P mają własność Q, to każdy pojedynczy obiekt o własności P będzie miał własność Q

uproszczenia

jeśli mamy kilka zmiennych z takimi samymi kwantyfikatorami

∀x∀yP(x,y)=∀x,yP(x,y) %%kwantyfikatory pod spodem%%

kwantyfikatory ograniczone

### dla dużego

∀x\[P(x)→Q(x)\] - %%wersja wyjściowa%%

**∀Q(x)**

**P(x)**

### dla małego

∃x\[P(x)→Q(x)\] - %%wersja wyjściowa%%

**∃Q(x)**

**P(x)**

* pierwszy(lub więcej) z brzegu predykat zapisujemy pod kwantyfikatorem
* zostaje nam jeden predykat po nim
* **przy małym zakładamy, że między predykatami jest koniunkcja**
* **przy dużym, że jest implikacja**

kwantyfikator ilościowy

∃!E(x), ∃1F(x) - istnieje jeden obiekt

∃nE(x) - istnieje n obiektów (wstaw dokładną liczbę)

\

dowodzenie

te same reguły co w rachunku zdań + reguły specyficzne dla rachunku predykatów

**nie można rozdzielać formuł skwantyfikowanych**

∀x\[P(x)→Q(x)\]

∀xP(x)

==nie można użyć reguły odrywania, bo formuła na górze jest całością, jest niepodzielna==

podstawianie stałej za zmienną

**można podstawiać tylko za zmienne wolne**

za tą samą zmienną zawsze podstawiamy tą samą stałą

**zmienna nie może zostać związana po podstawieniu**

x podstawione za y w R(x,y)

dostajemy R(x,x) - ==nie możemy dostać dwóch tych samych argumentów pod jednym predykatem==

opuszczanie kwantyfikatora ogólnego

**∀xP(x) - P(a)**

wyrażenie z kwantyfikatorem można zamienić na predykat z dowolna stałą

==nie można użyć stałej identycznej jak ta związana predykatem==

**∀y∃xP(x,x) Nope**

dołączanie kwantyfikatora ogólnego

**P(x) - ∀xP(x)**

==żadna zmienna w formule gdzie dołączamy nie może być wolna w założeniach dowodu==

dołączanie kwantyfikatora szczegółowego

P(x) - ∃xP(x)

mozna dolaczyc bez zadnych problemow

opuszczanie szczegółowego

∃xP(x) - P(a)

można podstawić nazwę, ale nie trzeba

==**taka sama nazwa nie może być wcześniej w dowodzie**==