Logika Intuicjonistyczna

Prowadzący: Michał Kotowski

O czym będą warsztaty

Prawo wyłączonego środka - "p lub nie p", dane zdanie jest prawdziwe albo fałszywe - jest prawem logiki, do której najbardziej chyba jesteśmy przyzwyczajeni. W I połowie XX wieku wymyślono tzw. logikę intuicjonistyczną, w której to prawo nie obowiązuje, podobnie jak wiele innych prawideł logiki klasycznej - nie można na przykład przeprowadzać "dowodów nie wprost". Na warsztatach opowiem, jak zbudowana jest logika intuicjonistyczna i jakie ma związki z matematyką oraz informatyką.

(Bardzo orientacyjny) program zajęć

-intuicjonistyczny rachunek zdań, interpretacja BHK
-modele Kripkego
-interpretacja topologiczna
-rachunek lambda a dowody intuicjonistyczne

Wymagania

Elementarna wiedza z logiki - znać zwykły, klasyczny rachunek zdań, umieć posługiwać się kwantyfikatorami, umieć stwierdzić, kiedy jakieś zdanie jest tautologią itd. Jeszcze lepiej, gdyby ktoś umiał trochę więcej, np. wiedział, co to jest model formuły logicznej i czym różni się zdanie prawdziwe od takiego, które posiada dowód, ale nie będę tego wymagał (ew. możemy przed warsztatami zrobić sobie jakieś krótkie wprowadzenie do logiki klasycznej).

Jeśli ktoś chciałby zaznajomić się lepiej z logiką klasyczną, polecam skrypt (autorstwa prof. Urzyczyna, Tiuryna i Tyszkiewicza z MIMUW).

Zadania kwalifikacyjne

Jeśli ktoś będzie miał jakieś wątpliwości dotyczące poniższych zadań, niech napisze. Zadania należy wysyłać na: moc.liamg|1ikswotok.lahcim#moc.liamg|1ikswotok.lahcim.

1. Zbadać, czy następujące formuły rachunku zdań są tautologiami i czy są spełnialne:

$((p \rightarrow r) \wedge (q \rightarrow s) \wedge (\neg p \vee \neg s)) \rightarrow (\neg p \vee \neg q)$
$q \vee r \rightarrow (p \vee q \rightarrow p \vee r)$

2. Zbadać, czy następujące formuły rachunku I rzędu są tautologiami i czy są spełnialne:

$\exists x \forall y (p(x) \vee q(y) ) \rightarrow \forall y (p(f(y)) \vee q(y))$
$\exists x (\forall y q(y) \rightarrow p(x)) \rightarrow \exists x \forall y (q(y) \rightarrow p(x))$

3. Dla każdej z par struktur wskazać zdanie, które jest prawdziwe w jednej z nich, a nie jest w drugiej:

$\langle \mathbb{N}, + \rangle$ i $\langle \mathbb{Z}, + \rangle$
$\langle \mathbb{N}, \leq \rangle$ i $\langle \{ m - \frac{1}{n} | m, n \in \mathbb{N}\setminus \{ 0 \} \}, \leq\rangle$

(zapis np. $\langle \mathbb{N}, + \rangle$ oznacza, że kwantyfikujemy po liczbach naturalnych i wolno nam używać w zdaniach jednej funkcji dwuargumentowej "+" itd.)

Uwagi

Temat ma pewien związek z gadającymi ptakami, o których warsztaty poprowadzi Janek Szejko.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License