Logika matematyczna

obowiązkowe

Główne cele przedmiotu to:

- Zapoznanie studentów z syntaktyką i semantyką klasycznego rachunku zdań (KRZ).

- Zapoznanie studentów z elementami teorii dowodu. Wnioskowanie w KRZ w ujęciu syntaktycznym i semantycznym. Pełność i rozstrzygalność KRZ.

- Zapoznanie studentów z syntaktyką klasycznego rachunku kwantyfikatorów (KRK). Wnioskowanie w KRK w ujęciu syntaktycznym.

- Zapoznanie studentów z podstawami teorii zbiorów i relacji oraz teorii funkcji i mocy.

- Zapoznanie studentów z zastosowaniami logiki i teorii mnogości w technice i nauce.

Przedmiot wymaga wiedzy z zakresu matematyki na poziomie szkoły ponadgimnazjalnej, w tym wiedzy z zakresu funkcji elementarnych i ich własności.

Przedmiot składa się z wykładu oraz ćwiczeń.

Główne tematy poruszane na wykładzie:

- Wprowadzenie podstawowych pojęć Klasycznego Rachunku Zdań. Zmienne zdaniowe, formuły, wartościowania zmiennych, prawa logiczne. Tautologie

i kontrtautologie KRZ.

- Metody sprawdzania tautologiczności formuł KRZ. Definiowalność spójników zdaniowych. Układy 2-zupełne oraz zupełne. Twierdzenie o podstawianiu.

- Postacie normalne i ich zastosowanie. Algorytmy przekształcania formuł zdaniowych, ich złożoność obliczeniowa i zastosowania. Automatyczne metody sprawdzania tautologiczności. SAT solvery i ich zastosowania.

- Główne typy rozumowań. Reguły dowodzenia, reguły dedukcji naturalnej. Dowód formalny formuły – wprost i nie wprost. Dowód - dodatkowe założenia.

- Wynikanie semantyczne i syntaktyczne. Reguły inferencyjne i pojęcie dowodu formalnego. Operacja konsekwencji. Podstawowe pojęcia teorii dowodu. Klasyczne systemy dedukcji naturalnej.

- Formy zdaniowe a zdania logiczne. Elementy rachunku kwantyfikatorów. Dowodzenie tautologii rachunku kwantyfikatorów.

- Drzewo formuły logicznej. Notacja polska, Odwrotna notacja polska. Logiki nieklasyczne i ich zastosowania w technice.

- Algebra zbiorów i jej własności. Zbiór potęgowy, podział zbioru. Algorytm wyznaczania podziałów zbioru.

- Algebra relacji. Suma, iloczyn, konwers relacji i ich własności.

- Typy relacji binarnych i ich własności. Relacje równoważności, zbiory ilorazowe. Zasada abstrakcji.

- Relacje częściowego porządku, struktury częściowo-porządkowe. Porządki liniowe oraz gęste. Drzewa jako struktury porządkowe, porządek leksykograficzny.

- Funkcje jako relacje. Powtórzenie informacji o funkcjach elementarnych. Operacje na funkcjach. Własności funkcji.

- Elementy teorii mocy. Zbiory przeliczalne i nieprzeliczalne. Liczby kardynalne. Uogólniona hipoteza continuum.

Ćwiczenia koncentrują się wokół tematyki związanej z:

- Drzewa konstrukcji formuł KRZ. Notacja polska. Dowodzenie tautologiczności formuł metodą tabelkową.

- Dowodzenie tautologiczności formuł KRZ metodą skróconą. Definiowalność spójników. Układy pełne (zupełne).

- Przekształcanie formuł KRZ. Sprowadzanie do postaci normalnych. Automatyczne metody sprawdzania tautologiczności.

- Wnioskowanie logiczne w systemie dedukcji naturalnej.

- Działania na zbiorach i relacjach.

- Badanie typów relacji binarnych. Dowodzenie zależności między typami. Wyznaczanie zbiorów ilorazowych.

1. Mordechai Ben-Ari, Logika matematyczna w informatyce, WNT, Warszawa 2005

2. Kazimierz Kuratowski, Wstęp do teorii mnogości i topologii, PWN, Warszawa 1980.

3. Wiktor Marek, Janusz Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach, PWN, Warszawa 1977.

4. Helena Rasiowa, Wstęp do matematyki współczesnej, PWN, Warszawa 1990.

5. H.J. Siegfried: Od teorii mnogości do algebry logiki, WKiŁ, Warszawa 1977

6. Jacek Cichoń, Marcin Gogolewski, Mirosław Kutyłowski, Logika dla informatyków, Wydawnictwo Wyższej Szkoły Komunikacji i Zarządzania, 2006

7. Andrzej Grzegorczyk, Zarys logiki matematycznej, Warszawa, PWN 1981.

8. Katarzyna Paprzycka, Logika nie gryzie, Część I Samouczek Logiki Zdań, Zysk i S-ka Wydawnictwo, Poznań 2009.

9. Witold Marciszewski (red.), Logika formalna. Zarys encyklopedyczny z zastosowaniem do informatyki i lingwistyki, Warszawa, PWN, 1987.

10. Kazimierz Kuratowski, Andrzej Mostowski, Teoria mnogości, PWN, Warszawa 1978.

11. Andrzej Mostowski, Logika matematyczna, Polska Biblioteka Wirtualna Nauki, tom 18 http://matwbn.icm.edu.pl/

12. Grygiel Joanna, Kurkowski Mirosław, Wybrane elementy logiki, teorii mnogości i teorii grafów, Oficyna Wydawnicza Europejskiej Uczelni, Warszawa 2015

13. Jerzy Słupecki, Ludwik Borkowski, Elementy logiki matematycznej i teorii mnogości, PWN, Warszawa 1963.

14. Andrzej Biela, Wstęp do logiki algorytmicznej, Wyd. Uniw. Śląskiego, 1995 (Opr. miękka, str. 248)

15. Nadiya M. Gubareni, Logika dla studentów, Wyd. Politechniki Częstochowskiej, 2002 (Opr. miękka, str. 276)

16. Kenneth A. Ross, Charles R. B. Wright, Matematyka dyskretna, PWN, Warszawa, 1986.

1. Student będzie potrafił zapisywać zdania języka potocznego i języka matematyki w języku rachunku zdań i rachunku kwantyfikatorów;

2. Student będzie potrafił przeprowadzać wnioskowania oraz sprawdzać ich poprawność zarówno metodami semantycznymi jak i

syntaktycznymi;

3. Student będzie potrafił dostrzegać struktury teorii mnogości i ich zastosowanie do opisu rzeczywistości;

4. Student będzie dostrzegał zastosowania logiki oraz teorii mnogości w technice i nauce.

W trakcie wykładu i ćwiczeń student potrafi zapisywać proste systemy w języku rachunku zdań i języku rachunku predykatów. Potrafi

przeprowadzać mniej lub bardziej złożone wnioskowania oraz sprawdzać ich poprawność.

Ponadto student potrafi dostrzegać mniej lub bardziej złożone struktury teorii mnogości w opisie rzeczywistości, konstruować złożone

przykłady i uzasadniać ich adekwatność. Głównym celem jest aby student dostrzegał i rozumiał problematykę zastosowań logiki w nauce

oraz technice.

Wykład kończy się sprawdzeniem wiadomości treści wykładu, forma sprawdzenia to test.

Zaliczenie ćwiczeń związane jest z zaliczeniem co najmniej dwóch kolokwiów sprawdzających umiejętności rozwiązywania zadań.