Logika u SAGE-u

verzija: SageMath 9.4

In [1]:
load('logika.sage')

import sage.logic.propcalc as logika
sage.logic.logicparser as logikapar
U paketu se nalaze funkcije:
tablica_istinitosti, semanticka_tablica, DNF, CNF, minDNF, minCNF

Funkcija bool

In [2]:
bool(True)
Out[2]:
True
In [3]:
bool(False)
Out[3]:
False
In [4]:
bool(2)
Out[4]:
True
In [5]:
bool([])
Out[5]:
False
In [6]:
bool(0)
Out[6]:
False
In [7]:
bool([0])
Out[7]:
True
In [8]:
bool([1,0,3])
Out[8]:
True
In [9]:
list(map(lambda x: bool(x),[1,0,3]))
Out[9]:
[True, False, True]

Možemo definirati svoju funkciju bul koja će se ponašati kao i funkcija bool, samo što će umjesto vrijednosti True i False vraćati vrijednosti 1 i 0.

In [10]:
def bul(x):
    if bool(x)==True:
        return 1
    else:
        return 0
In [11]:
bul(True)
Out[11]:
1
In [12]:
bul(False)
Out[12]:
0
In [13]:
bul(2)
Out[13]:
1
In [14]:
bul([])
Out[14]:
0
In [15]:
bul(0)
Out[15]:
0
In [16]:
bul([0])
Out[16]:
1
In [17]:
bul([1,0,3])
Out[17]:
1
In [18]:
list(map(lambda x: bul(x),[1,0,3]))
Out[18]:
[1, 0, 1]

Negacija

In [19]:
not(True)
Out[19]:
False
In [20]:
not(False)
Out[20]:
True
In [21]:
not(3)
Out[21]:
False
In [22]:
not([])
Out[22]:
True
In [23]:
not([0])
Out[23]:
False
In [24]:
not(0)
Out[24]:
True

Konjunkcija

In [25]:
True and False
Out[25]:
False
In [26]:
True & False
Out[26]:
False
In [27]:
1 & 0
Out[27]:
0
In [28]:
1 and 0
Out[28]:
0

Disjunkcija

In [29]:
False or True
Out[29]:
True
In [30]:
False | True
Out[30]:
True
In [31]:
0 | 1
Out[31]:
1
In [32]:
0 or 1
Out[32]:
1

Implikacija

In [33]:
def implikacija(x,y):
    return not(x) or y
In [34]:
implikacija(True,False)
Out[34]:
False
In [35]:
implikacija(1,0)
Out[35]:
0
In [36]:
implikacija(0,0)
Out[36]:
True
In [37]:
implikacija(False,False)
Out[37]:
True

Ekvivalencija

In [38]:
def ekvivalencija(x,y):
    return (not(x) or y) and (not(y) or x)
In [39]:
ekvivalencija(False,True)
Out[39]:
False
In [40]:
ekvivalencija(True,True)
Out[40]:
True
In [41]:
ekvivalencija(0,1)
Out[41]:
0
In [42]:
ekvivalencija(1,1)
Out[42]:
1

NOR

In [43]:
def NOR(x,y):
    return not(x or y)
In [44]:
NOR(True,False)
Out[44]:
False
In [45]:
NOR(False,False)
Out[45]:
True
In [46]:
NOR(1,0)
Out[46]:
False
In [47]:
NOR(0,0)
Out[47]:
True

NAND

In [48]:
def NAND(x,y):
    return not(x and y)
In [49]:
NAND(True,False)
Out[49]:
True
In [50]:
NAND(True,True)
Out[50]:
False
In [51]:
NAND(1,0)
Out[51]:
True
In [52]:
NAND(1,1)
Out[52]:
False

Ekskluzivno ili

In [53]:
def xor(x,y):
    return (x and not(y)) or (not(x) and y)
In [54]:
xor(True,False)
Out[54]:
True
In [55]:
xor(True,True)
Out[55]:
False
In [56]:
xor(1,0)
Out[56]:
True
In [57]:
xor(1,1)
Out[57]:
False

Tablice istinitosti

In [58]:
import sage.logic.propcalc as logika
import sage.logic.logicparser as logikapar

Konjunkcija

In [59]:
formula1=logika.formula('a&b')
In [60]:
formula1
Out[60]:
a&b
In [61]:
formula1.truthtable()
Out[61]:
a      b      value
False  False  False  
False  True   False  
True   False  False  
True   True   True
In [62]:
logika.formula('a&b').truthtable()
Out[62]:
a      b      value
False  False  False  
False  True   False  
True   False  False  
True   True   True

Disjunkcija

In [63]:
logika.formula('a|b')
Out[63]:
a|b
In [64]:
logika.formula('a|b').truthtable()
Out[64]:
a      b      value
False  False  False  
False  True   True   
True   False  True   
True   True   True

Negacija

In [65]:
logika.formula('~a')
Out[65]:
~a
In [66]:
logika.formula('~a').truthtable()
Out[66]:
a      value
False  True   
True   False

Implikacija

In [67]:
logika.formula('a->b')
Out[67]:
a->b
In [68]:
logika.formula('a->b').truthtable()
Out[68]:
a      b      value
False  False  True   
False  True   True   
True   False  False  
True   True   True

Ekvivalencija

In [69]:
logika.formula('a<->b')
Out[69]:
a<->b
In [70]:
logika.formula('a<->b').truthtable()
Out[70]:
a      b      value
False  False  True   
False  True   False  
True   False  False  
True   True   True

NOR

In [71]:
logika.formula('~(a|b)')
Out[71]:
~(a|b)
In [72]:
logika.formula('~(a|b)').truthtable()
Out[72]:
a      b      value
False  False  True   
False  True   False  
True   False  False  
True   True   False

NAND

In [73]:
logika.formula('~(a&b)')
Out[73]:
~(a&b)
In [74]:
logika.formula('~(a&b)').truthtable()
Out[74]:
a      b      value
False  False  True   
False  True   True   
True   False  True   
True   True   False

Ekskluzivno ili

In [75]:
logika.formula('a^b')
Out[75]:
a^b
In [76]:
logika.formula('a^b').truthtable()
Out[76]:
a      b      value
False  False  False  
False  True   True   
True   False  True   
True   True   False

Korištenje implementiranih funkcija

Primjer

Semantička tablica formule $F(x,y,z)=\big(\overline{y}\wedge z\big)\Leftrightarrow\big((x\Rightarrow y)\vee z\big)$.

In [77]:
semanticka_tablica('((~y)&z)<->((x->y)|z)')

x y z ~y (~y)&z x->y (x->y)|z ((~y)&z)<->((x->y)|z) 
---------------------------------------------------
1 1 1 0    0     1      1               0           
1 1 0 0    0     1      1               0           
1 0 1 1    1     0      1               1           
1 0 0 1    0     0      0               1           
0 1 1 0    0     1      1               0           
0 1 0 0    0     1      1               0           
0 0 1 1    1     1      1               1           
0 0 0 1    0     1      1               0
In [78]:
semanticka_tablica('((~y)&z)<->((x->y)|z)',izlaz="rjecnik")
Out[78]:
{'x': [1, 1, 1, 1, 0, 0, 0, 0],
 'y': [1, 1, 0, 0, 1, 1, 0, 0],
 'z': [1, 0, 1, 0, 1, 0, 1, 0],
 '~y': [0, 0, 1, 1, 0, 0, 1, 1],
 '(~y)&z': [0, 0, 1, 0, 0, 0, 1, 0],
 'x->y': [1, 1, 0, 0, 1, 1, 1, 1],
 '(x->y)|z': [1, 1, 1, 0, 1, 1, 1, 1],
 '((~y)&z)<->((x->y)|z)': [0, 0, 1, 1, 0, 0, 1, 0]}
In [79]:
semanticka_tablica('((~y)&z)<->((x->y)|z)',izlaz="html")
Out[79]:
\(x\) \(y\) \(z\) \(\neg y\) \((\neg y)\wedge z\) \(x\Rightarrow y\) \((x\Rightarrow y)\vee z\) \(((\neg y)\wedge z)\Leftrightarrow ((x\Rightarrow y)\vee z)\)
\(1\) \(1\) \(1\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(1\) \(1\) \(0\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(1\) \(0\) \(1\) \(1\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(0\) \(0\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(0\) \(1\) \(0\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(0\) \(0\) \(1\) \(1\) \(1\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(0\) \(1\) \(0\) \(1\) \(1\) \(0\)

Primjer

Semantička tablica formule $F(a,b,c,d)=\big((a\Rightarrow b)\wedge(b\Rightarrow c)\big)\Rightarrow(a\Leftrightarrow d)$.

In [80]:
semanticka_tablica('((a->b)&(b->c))->(a<->d)')

a b c d a->b b->c (a->b)&(b->c) a<->d ((a->b)&(b->c))->(a<->d) 
--------------------------------------------------------------
1 1 1 1  1    1         1         1              1             
1 1 1 0  1    1         1         0              0             
1 1 0 1  1    0         0         1              1             
1 1 0 0  1    0         0         0              1             
1 0 1 1  0    1         0         1              1             
1 0 1 0  0    1         0         0              1             
1 0 0 1  0    1         0         1              1             
1 0 0 0  0    1         0         0              1             
0 1 1 1  1    1         1         0              0             
0 1 1 0  1    1         1         1              1             
0 1 0 1  1    0         0         0              1             
0 1 0 0  1    0         0         1              1             
0 0 1 1  1    1         1         0              0             
0 0 1 0  1    1         1         1              1             
0 0 0 1  1    1         1         0              0             
0 0 0 0  1    1         1         1              1
In [81]:
semanticka_tablica('((a->b)&(b->c))->(a<->d)',izlaz="rjecnik")
Out[81]:
{'a': [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 'b': [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
 'c': [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
 'd': [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
 'a->b': [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
 'b->c': [1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1],
 '(a->b)&(b->c)': [1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1],
 'a<->d': [1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1],
 '((a->b)&(b->c))->(a<->d)': [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1]}
In [82]:
semanticka_tablica('((a->b)&(b->c))->(a<->d)',izlaz="html")
Out[82]:
\(a\) \(b\) \(c\) \(d\) \(a\Rightarrow b\) \(b\Rightarrow c\) \((a\Rightarrow b)\wedge (b\Rightarrow c)\) \(a\Leftrightarrow d\) \(((a\Rightarrow b)\wedge (b\Rightarrow c))\Rightarrow (a\Leftrightarrow d)\)
\(1\) \(1\) \(1\) \(1\) \(1\) \(1\) \(1\) \(1\) \(1\)
\(1\) \(1\) \(1\) \(0\) \(1\) \(1\) \(1\) \(0\) \(0\)
\(1\) \(1\) \(0\) \(1\) \(1\) \(0\) \(0\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(0\) \(1\) \(0\) \(0\) \(0\) \(1\)
\(1\) \(0\) \(1\) \(1\) \(0\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(1\) \(0\) \(0\) \(1\) \(0\) \(0\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(0\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(0\) \(0\) \(1\) \(0\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(1\) \(1\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(1\) \(1\) \(1\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(1\) \(1\) \(0\) \(0\) \(0\) \(1\)
\(0\) \(1\) \(0\) \(0\) \(1\) \(0\) \(0\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\) \(1\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(0\) \(1\) \(1\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(0\) \(1\) \(1\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(1\) \(1\) \(1\) \(1\) \(1\)

Primjer (De Morganovi zakoni)

Provjerimo da vrijede De Morganovi zakoni: $\overline{a\vee b}=\overline{a}\wedge\overline{b}$,   $\overline{a\wedge b}=\overline{a}\vee\overline{b}$.

In [83]:
tablica_istinitosti(['~(a|b)','(~a)&(~b)'])

a b ~(a|b) (~a)&(~b) 
--------------------
1 1   0        0     
1 0   0        0     
0 1   0        0     
0 0   1        1
In [84]:
tablica_istinitosti(['~(a&b)','(~a)|(~b)'],izlaz='html')
Out[84]:
\(a\) \(b\) \(\neg (a\wedge b)\) \((\neg a)\vee (\neg b)\)
\(1\) \(1\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(1\)
\(0\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(1\) \(1\)

Primjer (Distributivnost konjunkcije u odnosu na disjunkciju)

$a\wedge\big(b\vee c\big)=\big(a\wedge b\big)\vee\big(a\wedge c\big)$

In [85]:
tablica_istinitosti(['a&(b|c)','(a&b)|(a&c)'])

a b c a&(b|c) (a&b)|(a&c) 
-------------------------
1 1 1    1         1      
1 1 0    1         1      
1 0 1    1         1      
1 0 0    0         0      
0 1 1    0         0      
0 1 0    0         0      
0 0 1    0         0      
0 0 0    0         0
In [86]:
tablica_istinitosti(['a&(b|c)','(a&b)|(a&c)'],izlaz="html")
Out[86]:
\(a\) \(b\) \(c\) \(a\wedge (b\vee c)\) \((a\wedge b)\vee (a\wedge c)\)
\(1\) \(1\) \(1\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(0\)

Primjer (Distributivnost disjunkcije u odnosu na konjunkciju)

$a\vee\big(b\wedge c\big)=\big(a\vee b\big)\wedge\big(a\vee c\big)$

In [87]:
tablica_istinitosti(['a|(b&c)','(a|b)&(a|c)'])

a b c a|(b&c) (a|b)&(a|c) 
-------------------------
1 1 1    1         1      
1 1 0    1         1      
1 0 1    1         1      
1 0 0    1         1      
0 1 1    1         1      
0 1 0    0         0      
0 0 1    0         0      
0 0 0    0         0
In [88]:
tablica_istinitosti(['a|(b&c)','(a|b)&(a|c)'],izlaz="html")
Out[88]:
\(a\) \(b\) \(c\) \(a\vee (b\wedge c)\) \((a\vee b)\wedge (a\vee c)\)
\(1\) \(1\) \(1\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(1\)
\(0\) \(1\) \(1\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(0\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(0\)

Primjer (Tablice istinitosti logičkih operacija)

negacija

In [89]:
tablica_istinitosti(['~a'])

a ~a 
----
1 0  
0 1
In [90]:
tablica_istinitosti(['~a'],izlaz='html')
Out[90]:
\(a\) \(\neg a\)
\(1\) \(0\)
\(0\) \(1\)

konjunkcija

In [91]:
tablica_istinitosti(['a&b'])

a b a&b 
-------
1 1  1  
1 0  0  
0 1  0  
0 0  0
In [92]:
tablica_istinitosti(['a&b'],izlaz='html')
Out[92]:
\(a\) \(b\) \(a\wedge b\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(0\)
\(0\) \(1\) \(0\)
\(0\) \(0\) \(0\)

disjunkcija

In [93]:
tablica_istinitosti(['a|b'])

a b a|b 
-------
1 1  1  
1 0  1  
0 1  1  
0 0  0
In [94]:
tablica_istinitosti(['a|b'],izlaz='html')
Out[94]:
\(a\) \(b\) \(a\vee b\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(1\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(0\)

implikacija

In [95]:
tablica_istinitosti(['a->b'])

a b a->b 
--------
1 1  1   
1 0  0   
0 1  1   
0 0  1
In [96]:
tablica_istinitosti(['a->b'],izlaz='html')
Out[96]:
\(a\) \(b\) \(a\Rightarrow b\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(0\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(1\)

ekvivalencija

In [97]:
tablica_istinitosti(['a<->b'])

a b a<->b 
---------
1 1   1   
1 0   0   
0 1   0   
0 0   1
In [98]:
tablica_istinitosti(['a<->b'],izlaz='html')
Out[98]:
\(a\) \(b\) \(a\Leftrightarrow b\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(0\)
\(0\) \(1\) \(0\)
\(0\) \(0\) \(1\)

NOR

In [99]:
tablica_istinitosti(['~(a|b)'])

a b ~(a|b) 
----------
1 1   0    
1 0   0    
0 1   0    
0 0   1
In [100]:
tablica_istinitosti(['~(a|b)'],izlaz='html')
Out[100]:
\(a\) \(b\) \(\neg (a\vee b)\)
\(1\) \(1\) \(0\)
\(1\) \(0\) \(0\)
\(0\) \(1\) \(0\)
\(0\) \(0\) \(1\)

NAND

In [101]:
tablica_istinitosti(['~(a&b)'])

a b ~(a&b) 
----------
1 1   0    
1 0   1    
0 1   1    
0 0   1
In [102]:
tablica_istinitosti(['~(a&b)'],izlaz='html')
Out[102]:
\(a\) \(b\) \(\neg (a\wedge b)\)
\(1\) \(1\) \(0\)
\(1\) \(0\) \(1\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(1\)

ekskluzivno ili

In [103]:
tablica_istinitosti(['(a&(~b))|((~a)&b)'])

a b (a&(~b))|((~a)&b) 
---------------------
1 1         0         
1 0         1         
0 1         1         
0 0         0
In [104]:
tablica_istinitosti(['(a&(~b))|((~a)&b)'],izlaz='html')
Out[104]:
\(a\) \(b\) \((a\wedge (\neg b))\vee ((\neg a)\wedge b)\)
\(1\) \(1\) \(0\)
\(1\) \(0\) \(1\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(0\)

Ispitivanje istinitosti sudova

"4+7=10" je lažan sud

In [105]:
4+7==10
Out[105]:
False

"8 je paran broj" je istinit sud

In [106]:
is_even(8)
Out[106]:
True

"8 je neparan broj" je lažan sud

In [107]:
is_odd(8)
Out[107]:
False

"$\sqrt{15}$ je iracionalni broj" je istinit sud

In [108]:
sqrt(15) in QQ
Out[108]:
False

"2 nije prost broj" je lažan sud

In [109]:
is_prime(2)
Out[109]:
True
In [110]:
2 in Primes()
Out[110]:
True

"$(3<2)\wedge(2>1)$" je lažan sud

In [111]:
(3<2) & (2>1)
Out[111]:
False
In [112]:
(3<2) and (2>1)
Out[112]:
False

"$(3<2)\vee(2>1)$" je istinit sud

In [113]:
(3<2) | (2>1)
Out[113]:
True
In [114]:
(3<2) or (2>1)
Out[114]:
True

"$(3<2)\Rightarrow(2>1)$" je istinit sud

In [115]:
implikacija(3<2,2>1)
Out[115]:
True

"$(2>1)\Rightarrow(3<2)$" je lažan sud

In [116]:
implikacija(2>1,3<2)
Out[116]:
False

"$(3<2)\Leftrightarrow(2>1)$" je lažan sud

In [117]:
ekvivalencija(3<2,2>1)
Out[117]:
False

"Ako je $\pi\in\mathbb{Q}$ ili $5^2=25$, tada je $5^2=20$" je lažan sud

In [118]:
implikacija((pi in QQ) or (5^2==25),5^2==20)
Out[118]:
False

"Ako je $\pi\in\mathbb{Q}$ i $5^2=25$, tada je $5^2=20$" je istinit sud

In [119]:
implikacija((pi in QQ) and (5^2==25),5^2==20)
Out[119]:
True

"Ako 6 nije višekratnik broja 3, tada je 6 paran broj" je istinit sud

In [120]:
implikacija(Mod(6,3)!=0,is_even(6))
Out[120]:
True

"Ako je 2<3, tada je 2 prost i 3 je neparan" je istinit sud

In [121]:
implikacija(2<3,is_prime(2) and is_odd(3))
Out[121]:
True
In [122]:
implikacija(2<3,(2 in Primes()) and is_odd(3))
Out[122]:
True

Tautologija

Formula $a\Rightarrow\big(a\vee b\big)$ je tautologija

In [123]:
f1=logika.formula('a->(a|b)')
f1.is_tautology()
Out[123]:
True
In [124]:
tablica_istinitosti(['a->(a|b)'])

a b a->(a|b) 
------------
1 1    1     
1 0    1     
0 1    1     
0 0    1
In [125]:
tablica_istinitosti(['a->(a|b)'],izlaz='html')
Out[125]:
\(a\) \(b\) \(a\Rightarrow (a\vee b)\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(1\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(1\)

Formula $\big(a\wedge(a\Rightarrow b)\big)\Rightarrow b$ je tautologija (MODUS PONENS)

In [126]:
f2=logika.formula('(a&(a->b))->b')
f2.is_tautology()
Out[126]:
True
In [127]:
tablica_istinitosti(['(a&(a->b))->b'])

a b (a&(a->b))->b 
-----------------
1 1       1       
1 0       1       
0 1       1       
0 0       1
In [128]:
tablica_istinitosti(['(a&(a->b))->b'],izlaz='html')
Out[128]:
\(a\) \(b\) \((a\wedge (a\Rightarrow b))\Rightarrow b\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(1\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(1\)

Formula $\big((a\Rightarrow b)\wedge\overline{b}\big)\Rightarrow \overline{a}$ je tautologija (MODUS TOLENS)

In [129]:
f3=logika.formula('((a->b)&(~b))->(~a)')
f3.is_tautology()
Out[129]:
True
In [130]:
tablica_istinitosti(['((a->b)&(~b))->(~a)'])

a b ((a->b)&(~b))->(~a) 
-----------------------
1 1          1          
1 0          1          
0 1          1          
0 0          1
In [131]:
tablica_istinitosti(['((a->b)&(~b))->(~a)'],izlaz='html')
Out[131]:
\(a\) \(b\) \(((a\Rightarrow b)\wedge (\neg b))\Rightarrow (\neg a)\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(1\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(1\)

Formula $\big(\overline{a}\wedge(a\vee b)\big)\Rightarrow b$ je tautologija (DISJUNKTIVNI SILOGIZAM)

In [132]:
f4=logika.formula('((~a)&(a|b))->b')
f4.is_tautology()
Out[132]:
True
In [133]:
tablica_istinitosti(['((~a)&(a|b))->b'])

a b ((~a)&(a|b))->b 
-------------------
1 1        1        
1 0        1        
0 1        1        
0 0        1
In [134]:
tablica_istinitosti(['((~a)&(a|b))->b'],izlaz='html')
Out[134]:
\(a\) \(b\) \(((\neg a)\wedge (a\vee b))\Rightarrow b\)
\(1\) \(1\) \(1\)
\(1\) \(0\) \(1\)
\(0\) \(1\) \(1\)
\(0\) \(0\) \(1\)

Formula $\big((a\Rightarrow b)\wedge(b\Rightarrow c)\big)\Rightarrow(a\Rightarrow c)$ je tautologija (HIPOTETIČKI SILOGIZAM)

In [135]:
f5=logika.formula('((a->b)&(b->c))->(a->c)')
f5.is_tautology()
Out[135]:
True
In [136]:
tablica_istinitosti(['((a->b)&(b->c))->(a->c)'])

a b c ((a->b)&(b->c))->(a->c) 
-----------------------------
1 1 1            1            
1 1 0            1            
1 0 1            1            
1 0 0            1            
0 1 1            1            
0 1 0            1            
0 0 1            1            
0 0 0            1
In [137]:
tablica_istinitosti(['((a->b)&(b->c))->(a->c)'],izlaz='html')
Out[137]:
\(a\) \(b\) \(c\) \(((a\Rightarrow b)\wedge (b\Rightarrow c))\Rightarrow (a\Rightarrow c)\)
\(1\) \(1\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(1\)
\(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(1\)
\(0\) \(0\) \(1\) \(1\)
\(0\) \(0\) \(0\) \(1\)

Bazične konjunkcije i bazične disjunkcije

Zadatak

Jesu li konjunkcije $k_1=x\wedge y\wedge\overline{z}$  i  $k_2=x\wedge\overline{y}\wedge\overline{z}$ bazične konjunkcije formule $F(x,y,z)=\big((x\vee y)\wedge z\big)\Leftrightarrow\overline{x\wedge\overline{y}}$ ?

Rješenje. Uočimo da je $k_i$ bazična konjunkcija formule $F$ ako i samo ako je $k_i\Rightarrow F$ tautologija.

In [138]:
k1=logika.formula('x&y&(~z)')
k2=logika.formula('x&(~y)&(~z)')
F=logika.formula('((x|y)&z)<->(~(x&(~y)))')

$k_1$ nije bazična konjunkcija formule $F$

In [139]:
k1.ifthen(F).is_tautology()
Out[139]:
False
In [140]:
k1.add_statement(F,'->').is_tautology()
Out[140]:
False

$k_2$ jest bazična konjunkcija formule $F$

In [141]:
k2.ifthen(F).is_tautology()
Out[141]:
True
In [142]:
k2.add_statement(F,'->').is_tautology()
Out[142]:
True

Zadatak

Jesu li disjunkcije $d_1=\overline{x}\vee\overline{y}\vee z$ i $d_2=x\vee\overline{y}\vee\overline{z}$ bazične disjunkcije formule

$$F(x,y,z)=\big(y\Rightarrow((\overline{x}\vee y)\wedge z)\big)\Leftrightarrow\big(x\Rightarrow(\overline{z}\wedge y)\big)?$$

Rješenje. Uočimo da je $d_i$ bazična disjunkcija formule $F$ ako i samo ako je $F\Rightarrow d_i$ tautologija.

In [143]:
d1=logika.formula('(~x)|(~y)|z')
d2=logika.formula('x|(~y)|(~z)')
F=logika.formula('(y->(((~x)|y)&z))<->(x->((~z)&y))')

$d_1$ jest bazična disjunkcija formule $F$

In [144]:
F.ifthen(d1).is_tautology()
Out[144]:
True
In [145]:
F.add_statement(d1,'->').is_tautology()
Out[145]:
True

$d_2$ nije bazična disjunkcija formule $F$

In [146]:
F.ifthen(d2).is_tautology()
Out[146]:
False
In [147]:
F.add_statement(d2,'->').is_tautology()
Out[147]:
False

Minimizacija

Primjer

Disjunktivna i konjunktivna normalna forma funkcije $F(x,y,z)=\big((\overline{x}\vee z)\Leftrightarrow y\big)\Rightarrow\big(\overline{z}\Rightarrow(y\wedge z)\big)$ i njihove minimizacije.

In [148]:
DNF('((~x|z)<->y)->(~z->(y&z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\wedge y\wedge z)\vee (x\wedge y\wedge \neg z)\vee (x\wedge \neg y\wedge z)\vee (\neg x\wedge y\wedge z)\vee (\neg x\wedge \neg y\wedge z)\vee (\neg x\wedge \neg y\wedge \neg z)\]
In [149]:
CNF('((~x|z)<->y)->(~z->(y&z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(\neg x\vee y\vee z)\wedge (x\vee \neg y\vee z)\]
In [150]:
minDNF('((~x|z)<->y)->(~z->(y&z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}z\vee (x\wedge y)\vee (\neg x\wedge \neg y)\]
In [151]:
minCNF('((~x|z)<->y)->(~z->(y&z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\vee \neg y\vee z)\wedge (\neg x\vee y\vee z)\]

Primjer

Disjunktivna i konjunktivna normalna forma funkcije $F(x,y,z)=\big((x\wedge\overline{y})\vee z\big)\Leftrightarrow\big((y\wedge z)\Rightarrow(\overline{x}\wedge{y})\big)$ i njihove minimizacije.

In [152]:
DNF('((x&~y)|z)<->((y&z)->(~x&y))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\wedge \neg y\wedge z)\vee (x\wedge \neg y\wedge \neg z)\vee (\neg x\wedge y\wedge z)\vee (\neg x\wedge \neg y\wedge z)\]
In [153]:
CNF('((x&~y)|z)<->((y&z)->(~x&y))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(\neg x\vee \neg y\vee \neg z)\wedge (\neg x\vee \neg y\vee z)\wedge (x\vee \neg y\vee z)\wedge (x\vee y\vee z)\]
In [154]:
minDNF('((x&~y)|z)<->((y&z)->(~x&y))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(\neg x\wedge z)\vee (x\wedge \neg y)\]
In [155]:
minCNF('((x&~y)|z)<->((y&z)->(~x&y))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\vee z)\wedge (\neg x\vee \neg y)\]

provjera preko tablice istinitosti

In [156]:
tablica_istinitosti(['(~x&z)|(x&~y)','(~x|~y)&(x|z)','((x&~y)|z)<->((y&z)->(~x&y))'])

x y z (~x&z)|(x&~y) (~x|~y)&(x|z) ((x&~y)|z)<->((y&z)->(~x&y)) 
--------------------------------------------------------------
1 1 1       0             0                    0               
1 1 0       0             0                    0               
1 0 1       1             1                    1               
1 0 0       1             1                    1               
0 1 1       1             1                    1               
0 1 0       0             0                    0               
0 0 1       1             1                    1               
0 0 0       0             0                    0
In [157]:
tablica_istinitosti(['(~x&z)|(x&~y)','(~x|~y)&(x|z)','((x&~y)|z)<->((y&z)->(~x&y))'],izlaz='html')
Out[157]:
\(x\) \(y\) \(z\) \((\neg x\wedge z)\vee (x\wedge \neg y)\) \((\neg x\vee \neg y)\wedge (x\vee z)\) \(((x\wedge \neg y)\vee z)\Leftrightarrow ((y\wedge z)\Rightarrow (\neg x\wedge y))\)
\(1\) \(1\) \(1\) \(0\) \(0\) \(0\)
\(1\) \(1\) \(0\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(1\) \(1\)
\(0\) \(1\) \(1\) \(1\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(0\) \(0\) \(0\) \(0\)

Primjer

Disjunktivna i konjunktivna normalna forma funkcije $F(x,y,z)=\big((\overline{y}\wedge z)\Rightarrow(x\wedge\overline{z})\big)\Leftrightarrow\big(y\wedge(\overline{x}\vee z)\big)$ i njihove minimizacije.

In [158]:
DNF('((~y&z)->(x&~z))<->(y&(~x|z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\wedge y\wedge z)\vee (x\wedge \neg y\wedge z)\vee (\neg x\wedge y\wedge z)\vee (\neg x\wedge y\wedge \neg z)\vee (\neg x\wedge \neg y\wedge z)\]
In [159]:
CNF('((~y&z)->(x&~z))<->(y&(~x|z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(\neg x\vee \neg y\vee z)\wedge (\neg x\vee y\vee z)\wedge (x\vee y\vee z)\]
In [160]:
minDNF('((~y&z)->(x&~z))<->(y&(~x|z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}z\vee (\neg x\wedge y)\]
In [161]:
minCNF('((~y&z)->(x&~z))<->(y&(~x|z))')
\[\newcommand{\Bold}[1]{\mathbf{#1}}(y\vee z)\wedge (\neg x\vee z)\]

Zadatak

Za formulu $F(x,y,z)=\big(\overline{y}\wedge z\big)\Leftrightarrow\big((x\Rightarrow y)\vee z\big)$ izradite semantičku tablicu, odredite disjunktivnu i konjunktivnu normalnu formu i minimizirajte formulu $F$.

In [162]:
F='((~y)&z)<->((x->y)|z)'
In [163]:
semanticka_tablica(F)

x y z ~y (~y)&z x->y (x->y)|z ((~y)&z)<->((x->y)|z) 
---------------------------------------------------
1 1 1 0    0     1      1               0           
1 1 0 0    0     1      1               0           
1 0 1 1    1     0      1               1           
1 0 0 1    0     0      0               1           
0 1 1 0    0     1      1               0           
0 1 0 0    0     1      1               0           
0 0 1 1    1     1      1               1           
0 0 0 1    0     1      1               0
In [164]:
semanticka_tablica(F,izlaz='html')
Out[164]:
\(x\) \(y\) \(z\) \(\neg y\) \((\neg y)\wedge z\) \(x\Rightarrow y\) \((x\Rightarrow y)\vee z\) \(((\neg y)\wedge z)\Leftrightarrow ((x\Rightarrow y)\vee z)\)
\(1\) \(1\) \(1\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(1\) \(1\) \(0\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(1\) \(0\) \(1\) \(1\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(0\) \(0\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(0\) \(1\) \(0\) \(0\) \(0\) \(1\) \(1\) \(0\)
\(0\) \(0\) \(1\) \(1\) \(1\) \(1\) \(1\) \(1\)
\(0\) \(0\) \(0\) \(1\) \(0\) \(1\) \(1\) \(0\)
In [165]:
DNF(F)
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\wedge \neg y\wedge z)\vee (x\wedge \neg y\wedge \neg z)\vee (\neg x\wedge \neg y\wedge z)\]
In [166]:
CNF(F)
\[\newcommand{\Bold}[1]{\mathbf{#1}}(\neg x\vee \neg y\vee \neg z)\wedge (\neg x\vee \neg y\vee z)\wedge (x\vee \neg y\vee \neg z)\wedge (x\vee \neg y\vee z)\wedge (x\vee y\vee z)\]
In [167]:
minDNF(F)
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\wedge \neg y)\vee (\neg y\wedge z)\]
In [168]:
minCNF(F)
\[\newcommand{\Bold}[1]{\mathbf{#1}}(x\vee z)\wedge \neg y\]
In [ ]: