Logika matematyczna

Zdanie logiczne to każde stwierdzenie, któremu można przypisać dokładnie jedną z dwóch ocen: prawdę albo fałsz Oceny te nazywamy wartościami logicznymi zdania.
Jeśli zdanie jest prawdziwe, to jego wartość logiczną oznaczamy cyfrą 1.
Jeśli zdanie jest fałszywe, to jego wartość logiczną oznaczamy cyfrą 0.
Zdania oznaczamy małymi literami alfabetu łacińskiego p, q, r itp. lub greckiego α,ß,g.
Wyrażenie φ(x) nazywamy funkcją zdaniową z jedną zmienną x określoną na zbiorze X, jeżeli staje się ono zdaniem, gdy w miejsce x podstawimy dowolny element zbioru X.
Zbiór X nazywamy dziedziną funkcji zdaniowej φ(x).
Element a Î X spełnia funkcję zdaniową φ(x), jeżeli zdanie φ(x) jest prawdziwe.
Każde równanie i każda nierówność jest funkcją zdaniową.
Spójnik zdaniowy (spójnik logiczny, funktor zdaniotwórczy ) to zwrot lub symbol, za pomocą którego z danych zdań lub funkcji zdaniowych można utworzyć nowe zdania złożone lub nowe funkcje zdaniowe.

 

zwrot

symbol

"nieprawda że "

~

"lub"

Ú

"i"

Ů

"jeżeli...to"

Ţ

"wtedy i tylko wtedy"

Ű

 
 

 

 

Podstawowe zdania złożone

 

zdanie

czytamy

nazwa utworzonego zdania

~ p

nieprawda, że

zaprzeczenie (negacja) zdania p

p Ú q

p lub q

alternatywa zdań p i q

p Ů q

p i q

koniunkcja zdań p i q

p Ţ q

jeżeli p to q

implikacja zdań p i q

p Ű q

p wtedy i tylko wtedy, gdy q

równoważność zdań p i q

 
W zdaniu złożonym p Ţ q zdanie p nazywamy poprzednikiem implikacji, a zdanie q następnikiem implikacji.
Jeżeli równoważność p Ű q jest prawdziwa, to zdanie p oraz q nazywamy równoważnymi.

 

 

Tabele wartości logicznych podstawowych zdań złożonych

 

ALTERNATYWA

p

q

pÚq

1

1

1

1

0

1

0

1

1

0

0

0

KONIUNKCJA

p

q

pŮq

1

1

1

1

0

0

0

1

0

0

0

0

 

IMPLIKACJA

p

q

p Ţ q

1

1

1

1

0

0

0

1

1

0

0

1

 

RÓWOWAŻNOŚĆ

p

q

p Ű q

1

1

1

1

0

0

0

1

0

0

0

1

 
NEGACJA
p ~ p
1 0
0 1

 
 

   
Prawem rachunku zdań lub tautologią nazywamy schemat w którym niezależnie od wartości logicznych zdań, podstawianych do schematu zdania założonego w miejsce symboli zdaniowych, otrzymujemy zawsze zdanie prawdziwe.
   

 
 

Niektóre prawa rachunku zdań
 
 

p Ú ~ p

prawo wyłączonego środka

~ (~ p ) Ű p

prawo podwójnego przeczenia

~ ( p Ú q ) Ű ( ~p Ů ~ q )

prawo zaprzeczenia alternatywy( prawo de Morgana)

~ ( p Ů q ) Ű ( ~ p Ú ~ q )

prawo zaprzeczenia koniunkcji ( prawo de Morgana )

~( p Ţ q ) Ű ( p Ů ~ q )

prawo zaprzeczenia implikacji

( p Ţ q ) Ű ( ~ q Ţ ~ p )

prawo kontrapozycji

[( p Ţ q ) Ů ( q Ţ r)] Ţ ( p Ţ r )

prawo przechodniości implikacji

 

 
 

Kwantyfikatory
   
 
zwrot nazwa Oznaczenia
dla każdego x należącego do X" Kwantyfikator ogólny (duży)
 lub "x Î X
"istnieje taki x należący do X, że" Kwantyfikator szczegółowy ( mały )
 lub $ x Î X

Prawa de Morgana dla kwantyfikatorów
 

~

[p(x)]

Ű

[ ~ p(x)]

~

[p(x)]

Ű

[ ~ p(x)]
 

 
Pojęcie pierwotne - podstawowe proste pojęcie matematyczne, którego nie definiuje się, które należy rozumieć intuicyjnie.
Aksjomat (pewnik) - zdanie opisujące podstawowe zależności między pojęciami pierwotnymi, które uznawane jest za prawdziwe i przyjmowane bez dowodu.
Definicja - zdanie, które określa nowe pojęcie matematyczne.
Hipoteza - zdanie wyrażające pewne przypuszczenie, jeszcze nieudowodnione (być może fałszywe).
Dowód - uzasadnienie pewnej własności ( hipotezy) w oparciu o przyjęte aksjomaty,  wcześniej udowodnione twierdzenia i jej zasady logiki.
Twierdzenie - zdanie opisujące pewne zależności między pojęciami matematycznymi, którego prawdziwość została udowodniona.
Twierdzenia na ogół mają postać implikacji α Ţ ß lub postać równoważności α Ű ß.
Jeżeli twierdzenie ma postać implikacji α Ţ ß, to zdanie α nazywamy założeniem twierdzenia, a zdanie ß; tezą twierdzenia α Ţ ß jest zdaniem prawdziwym ( twierdzeniem).
Jeżeli zdanie ß Ţ α też jest prawdziwe, to nazywamy je twierdzeniem odwrotnym do twierdzenia α Ţ ß . Wówczas zachodzi twierdzenie α Ű ß (forma równoważności).
Jeśli zdanie α Ţ ß jest twierdzeniem, to zdanie  ~ß Ţ ~α  też jest twierdzeniem i nazywamy je twierdzeniem przeciwstawnym do twierdzenia  α Ţ ß.
Jeśli zachodzi twierdzenie ß Ţ α, odwrotne do twierdzenia α Ţ ß, to również zdanie  ~α Ţ ~ß jest twierdzeniem i nazywamy je twierdzeniem przeciwstawnym do twierdzenia  α Ţ ß.
   
 

   
Zasada indukcji matematycznej to metoda dowodzenia twierdzeń dotyczących liczb naturalnych.
  Zasada indukcji matematycznej (I)
  Niech W będzie pewną własnością dotyczącą liczb naturalnych.

Jeśli spełnione są warunki:

1.  liczba 0 ma własność W

2. dla każdej liczby naturalnej k z tego, że k ma własność W wynika, że własność tę ma również  liczba  k+1 to każda liczba naturalna ma własność W.
   
  Zasada indukcji matematycznej (II- uogólnienie)
  Niech W będzie pewną własnością dotyczącą liczb naturalnych.

Jeśli spełnione są warunki:

 1.  liczba naturalna k0 ma własność W

 2.  dla każdej liczby naturalnej k  z tego, że k ma własność W wynika, że własność tę ma również liczba  k+1 to  każda liczba naturalna ma własność W.

 
  Uwaga. Na ogół k0 = 0 jak w (I) lub k0 = 1.
Pkt 1. w zasadzie indukcji matematycznej nosi nazwę pierwszego kroku indukcyjnego.
 Pkt 2. nazywamy drugim krokiem indukcyjnym.
  W drugim kroku indukcyjnym występuje założenie indukcyjne ( założenie dotyczące liczby k) oraz    teza indukcyjna ( wniosek dotyczący liczby k+1).
Dowód twierdzenia przeprowadzony w oparciu o zasadę indukcji matematycznej nazywamy dowodem indukcyjnym.