Matematyka dyskretna - logika zdań

Reguły logiki matematycznej określają metody wnioskowania twierdzeń matematycznych. Grecki filozof Arystoteles był pionierem logicznego rozumowania. Logiczne rozumowanie stanowi podstawę teoretyczną dla wielu dziedzin matematyki, a co za tym idzie informatyki. Ma wiele praktycznych zastosowań w informatyce, takich jak projektowanie maszyn obliczeniowych, sztuczna inteligencja, definiowanie struktur danych dla języków programowania itp.

Propositional Logicdotyczy stwierdzeń, którym można przypisać wartości prawdy, „prawda” i „fałsz”. Celem jest przeanalizowanie tych stwierdzeń indywidualnie lub w sposób złożony.

Logika przyimkowa - definicja

Zdanie to zbiór zdań deklaratywnych, które mają albo wartość prawdziwości „prawda”, albo wartość prawdy „fałsz”. Zdanie składa się ze zmiennych zdaniowych i łączników. Zmienne zdaniowe oznaczamy dużymi literami (A, B itd.). Łączniki łączą zmienne zdaniowe.

Poniżej podano kilka przykładów twierdzeń -

  • „Człowiek jest śmiertelny”, zwraca wartość prawdy „PRAWDA”
  • „12 + 9 = 3 - 2”, zwraca wartość prawdy „FALSE”

Poniższe nie jest propozycją -

  • „A jest mniejsze niż 2”. Dzieje się tak, ponieważ dopóki nie podamy określonej wartości A, nie możemy powiedzieć, czy stwierdzenie jest prawdziwe czy fałszywe.

Połączenia

W logice zdań generalnie używamy pięciu połączeń, które są -

  • LUB ($ \ lor $)

  • AND ($ \ land $)

  • Negacja / NIE ($ \ lnot $)

  • Implikacja / jeśli-to ($ \ rightarrow $)

  • Jeśli i tylko wtedy, gdy ($ \ Leftrightarrow $).

OR ($\lor$) - Operacja OR dwóch zdań A i B (zapisanych jako $ A \ l lub B $) jest prawdą, jeśli przynajmniej którakolwiek ze zmiennych zdań A lub B jest prawdziwa.

Tabela prawdy jest następująca -

ZA b A ∨ B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Prawdziwe
Fałszywy Prawdziwe Prawdziwe
Fałszywy Fałszywy Fałszywy

AND ($\land$) - Operacja AND dwóch zdań A i B (zapisanych jako $ A \ land B $) jest prawdą, jeśli obie zmienne zdań A i B są prawdziwe.

Tabela prawdy jest następująca -

ZA b A ∧ B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Fałszywy
Fałszywy Fałszywy Fałszywy

Negation ($\lnot$) - Negacja zdania A (zapisanego jako $ \ lnot A $) jest fałszem, gdy A jest prawdą, i jest prawdziwą, gdy A jest fałszem.

Tabela prawdy jest następująca -

ZA ¬ A
Prawdziwe Fałszywy
Fałszywy Prawdziwe

Implication / if-then ($\rightarrow$)- Implikacją $ A \ rightarrow B $ jest zdanie „jeśli A, to B”. Jest fałszem, jeśli A jest prawdą, a B jest fałszem. Pozostałe przypadki są prawdziwe.

Tabela prawdy jest następująca -

ZA b A → B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Prawdziwe
Fałszywy Fałszywy Prawdziwe

If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ jest dwuwarunkowym łącznikiem logicznym, który jest prawdą, gdy p i q są takie same, tj. Oba są fałszywe lub oba są prawdziwe.

Tabela prawdy jest następująca -

ZA b A ⇔ B
Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Fałszywy
Fałszywy Fałszywy Prawdziwe

Tautologie

Tautologia to formuła, która jest zawsze prawdziwa dla każdej wartości jej zmiennych zdaniowych.

Example - Udowodnij, że $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ jest tautologią

Tabela prawdy jest następująca -

ZA b A → B (A → B) ∧ A [(A → B) ∧ A] → B
Prawdziwe Prawdziwe Prawdziwe Prawdziwe Prawdziwe
Prawdziwe Fałszywy Fałszywy Fałszywy Prawdziwe
Fałszywy Prawdziwe Prawdziwe Fałszywy Prawdziwe
Fałszywy Fałszywy Prawdziwe Fałszywy Prawdziwe

Jak widzimy, każda wartość $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ jest „True”, jest to tautologia.

Sprzeczności

Sprzeczność to formuła, która zawsze jest fałszywa dla każdej wartości jej zmiennych zdaniowych.

Example - Udowodnij, że $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ jest sprzecznością

Tabela prawdy jest następująca -

ZA b A ∨ B ¬ A ¬ B. (¬ A) ∧ (¬ B) (A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy Fałszywy Fałszywy
Prawdziwe Fałszywy Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy Fałszywy
Fałszywy Fałszywy Fałszywy Prawdziwe Prawdziwe Prawdziwe Fałszywy

Jak widzimy, każda wartość $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ to „Fałsz”, jest to sprzeczność.

Przypadkowość

Zależność jest formułą, która ma zarówno pewne wartości prawdziwe, jak i pewne fałszywe dla każdej wartości swoich zmiennych propozycyjnych.

Example - Udowodnij, że $ (A \ lor B) \ land (\ lnot A) $ jest przypadkiem

Tabela prawdy jest następująca -

ZA b A ∨ B ¬ A (A ∨ B) ∧ (¬ A)
Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy
Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy
Fałszywy Prawdziwe Prawdziwe Prawdziwe Prawdziwe
Fałszywy Fałszywy Fałszywy Prawdziwe Fałszywy

Jak widzimy, każda wartość $ (A \ lor B) \ land (\ lnot A) $ ma zarówno „Prawda”, jak i „Fałsz”, jest to przypadek.

Równoważności zdań

Dwie instrukcje X i Y są logicznie równoważne, jeśli zachodzi którykolwiek z poniższych dwóch warunków -

  • Tabele prawdy każdego stwierdzenia mają te same wartości prawdy.

  • Instrukcja dwuwarunkowa $ X \ Leftrightarrow Y $ jest tautologią.

Example - Udowodnij, że $ \ lnot (A \ lor B) i \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ są równoważne

Testowanie pierwszą metodą (pasująca tabela prawdy)

ZA b A ∨ B ¬ (A ∨ B) ¬ A ¬ B. [(¬ A) ∧ (¬ B)]
Prawdziwe Prawdziwe Prawdziwe Fałszywy Fałszywy Fałszywy Fałszywy
Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy Prawdziwe Fałszywy
Fałszywy Prawdziwe Prawdziwe Fałszywy Prawdziwe Fałszywy Fałszywy
Fałszywy Fałszywy Fałszywy Prawdziwe Prawdziwe Prawdziwe Prawdziwe

Tutaj widzimy, że wartości prawdy $ \ lnot (A \ lor B) i \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ są takie same, stąd stwierdzenia są równoważne.

Testowanie przy 2 -go metodą (Bi uwarunkowania)

ZA b ¬ (A ∨ B) [(¬ A) ∧ (¬ B)] [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
Prawdziwe Prawdziwe Fałszywy Fałszywy Prawdziwe
Prawdziwe Fałszywy Fałszywy Fałszywy Prawdziwe
Fałszywy Prawdziwe Fałszywy Fałszywy Prawdziwe
Fałszywy Fałszywy Prawdziwe Prawdziwe Prawdziwe

Ponieważ $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ jest tautologią, instrukcje są równoważne.

Odwrotność, konwersja i przeciwdziałanie dodatnim

Implikacja / jeśli-to $ (\ rightarrow) $ jest również nazywana instrukcją warunkową. Składa się z dwóch części -

  • Hipoteza, s
  • Wniosek, q

Jak wspomniano wcześniej, jest oznaczony jako $ p \ rightarrow q $.

Example of Conditional Statement- „Jeśli odrobisz pracę domową, nie zostaniesz ukarany”. Tutaj „odrabiasz pracę domową” to hipoteza, p, a „nie zostaniesz ukarany” to konkluzja, q.

Inverse- Odwrotnością zdania warunkowego jest zaprzeczenie zarówno hipotezy, jak i wniosku. Jeśli stwierdzeniem jest „Jeśli p, to q”, odwrotnością będzie „Jeśli nie p, to nie q”. Zatem odwrotnością $ p \ rightarrow q $ jest $ \ lnot p \ rightarrow \ lnot q $.

Example - Odwrotność „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany”, to „Jeśli nie odrabiasz pracy domowej, zostaniesz ukarany”.

Converse- Odwrotność zdania warunkowego jest obliczana poprzez zamianę hipotezy i wniosku. Jeśli stwierdzeniem jest „Jeśli p, to q”, odwrotnością będzie „Jeśli q, to ​​p”. Odwrotność $ p \ rightarrow q $ to $ q \ rightarrow p $.

Example - Odwrotność: „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany”, brzmi: „Jeśli nie zostaniesz ukarany, odrabiasz lekcje”.

Contra-positive- Przeciwwskazanie warunku jest obliczane poprzez zamianę hipotezy i wniosku ze stwierdzenia odwrotnego. Jeśli stwierdzeniem jest „Jeśli p, to q”, wynikiem przeciwstawnym będzie „Jeśli nie q, to ​​nie p”. Przeciwwskazanie $ p \ rightarrow q $ to $ \ lnot q \ rightarrow \ lnot p $.

Example - Przeciwstawne stwierdzenie „Jeśli odrabiasz pracę domową, nie zostaniesz ukarany” to „Jeśli zostaniesz ukarany, nie odrobiłeś pracy domowej”.

Zasada dwoistości

Zasada dwoistości mówi, że dla każdego prawdziwego stwierdzenia, podwójne stwierdzenie uzyskane przez zamianę związków na przecięcia (i odwrotnie) i zamianę zbioru uniwersalnego na zbiór zerowy (i odwrotnie) jest również prawdziwe. Jeśli podwójne w jakimkolwiek stwierdzeniu jest samo stwierdzenie, to jest powiedzianeself-dual komunikat.

Example - Podwójna wartość $ (A \ cap B) \ cup C $ to $ (A \ cup B) \ cap C $

Formy normalne

Możemy przekształcić dowolne zdanie w dwie normalne formy -

  • Postać normalna koniunkcyjna
  • Rozłączna postać normalna

Koniunkcyjna forma normalna

Zdanie złożone ma postać normalną koniunkcji, jeśli jest otrzymywane przez operację AND między zmiennymi (w tym negacja zmiennych) związanymi z OR. Pod względem operacji na zbiorach jest to instrukcja złożona uzyskana przez Przecięcie między zmiennymi związanymi ze Związkami.

Examples

  • $ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $

  • $ (P \ cup Q) \ cap (Q \ cup R) $

Rozłączna postać normalna

Instrukcja złożona ma rozłączną postać normalną, jeśli jest otrzymywana przez operację LUB pomiędzy zmiennymi (łącznie z negacją zmiennych) związanymi z AND. Pod względem operacji na zbiorach jest to złożona instrukcja uzyskiwana przez Union wśród zmiennych związanych z przecięciami.

Examples

  • $ (A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D) $

  • $ (P \ cap Q) \ cup (Q \ cap R) $