1
ﻓﺼﻞ
ﮔﺰارهﻫﺎ و ﻣﻨﻄﻖ رﻳﺎﺿﻲ
ﻣﻘﺪﻣﻪ 1-1
ﻣﻨﻄﻖ ﻣﺠﻤﻮﻋﻪ ﻗﻮاﻋﺪی اﺳﺖ ﻛﻪ ﺑﻪ ﻛﻤﻚ آﻧﻬﺎ ﻣﻲ ﺗﻮان اﻋﺘﺒﺎر ﻳﻚ اﺳﺘﺪﻻل را ﺗﻌﻴﻴﻦ ﻧﻤﻮد. ﺑﺮای اﺛﺒﺎت ﻗﻀﺎﻳﺎ ﻣﻲ ﺗﻮان از روش ﻫﺎی
ﻣﻨﻄﻖ اﺳﺘﻔﺎده ﻛﺮد. در اﻳﻦ ﻓﺼﻞ اﺑﺘﺪا ﺗﻌﺮﻳﻔﻲ از ﮔﺰاره ﻫﺎ و ﺳﭙﺲ ﻗﻮاﻧﻴﻦ و ﻣﺜﺎلﻫﺎی اﺳﺘﻔﺎده از آنﻫﺎ را ﺑﻴﺎن ﻣﻲﻛﻨﻴﻢ.
ﮔﺰارهﻫﺎ 2-1
ﮔﺰاره
: ﮔﺰاره ﺟﻤﻠﻪای اﺳﺖ ﺧﺒﺮی ﻛﻪ ارزش آن ﻳﺎ درﺳﺖ (T) ﻳﺎ ﻏﻠﻂ (F) اﺳﺖ و در آن واﺣﺪ ﻧﻤﻲﺗﻮاﻧﺪ ﻫﺮ دو ﺑﺎﺷﺪ. ﺑﻪ ﻋﻨﻮان ﻣﺜﺎل 1
ﻋﺒﺎرت «ﻋﺪد 8 ﺗﻮاﻧﻲ از ﻋﺪد 2 اﺳﺖ» ﻳﻚ ﮔﺰاره اﺳﺖ وﻟﻲ ﻋﺒﺎرت «ﺣﺎﺻﻞ اﻳﻦ ﺗﻘﺴﻴﻢ ﭼﻨﺪ اﺳﺖ؟» ﮔﺰاره ﻧﻴﺴﺖ.
ﻣﻌﻤﻮﻻً ﮔﺰارهﻫﺎ را ﺑﻪ ﺻﻮرت ﻧﻤﺎدﻳﻦ، ﺑﺎ ﺣﺮوف ﻛﻮﭼﻚ اﻧﮕﻠﻴﺴﻲ ﻧﻤﺎﻳﺶ ﻣﻲدﻫﻨﺪ.
اﻧﻮاع ﮔﺰارهﻫﺎ
ﮔﺰارهﻫﺎ را ﺑﻪ دو دﺳﺘﻪ ﺗﻘﺴﻴﻢ ﻛﺮدهاﻧﺪ:
: ﮔﺰارهای اﺳﺖ ﻛﻪ ﻗﺎﺑﻞ ﺗﺠﺰﻳﻪ ﺑﻪ ﮔﺰاره ﻫﺎی ﻛﻮﭼﻜﺘﺮ ﻧﺒﺎﺷﺪ. 2 ﮔﺰاره ﺳﺎده
: ﮔﺰارهای اﺳﺖ ﻛﻪ ﻣﺘﺸﻜﻞ از دو ﻳﺎ ﺑﻴﺸﺘﺮ از دو ﮔﺰاره ﺳﺎده ﺑﺎﺷﺪ ﻛﻪ ﺗﺮﻛﻴﺐ ﮔﺰارهﻫﺎی ﺳﺎده ﺑﺎ اﺳﺘﻔﺎده از راﺑﻄﻪ ﻫﺎی 3 ﮔﺰاره ﻣﺮﻛﺐ
ﻣﻨﻄﻘﻲ (ﻛﻪ در ﻗﺴﻤﺖ ﺑﻌﺪی ﺗﻮﺿﻴﺢ داده ﺷﺪه) ﺻﻮرت ﻣﻲﮔﻴﺮد.
1
Statement
2
Primitive statement
3
Compound
2
3
Compound
2
ﺳﺎﺧﺘﻤﺎنﻫﺎی ﮔﺴﺴﺘﻪ / ﻓﺼﻞ اول
ﮔﺰارهﻧﻤﺎ: ﻋﺒﺎرﺗﻲ ﻛﻪ ﺑﻪ ازای ﺑﻌﻀﻲ ﻣﻘﺎدﻳﺮ ارزش درﺳﺖ و ﺑﻪ ازای ﺑﻌﻀﻲ دﻳﮕﺮ ارزش ﻧﺎدرﺳﺖ داﺷﺘﻪ ﺑﺎﺷﺪ را ﻋﺒﺎرت ﮔﺰارهﻧﻤﺎ
ﻣﻲﮔﻮﻳﻨﺪ ﺑﻪ ﻋﻨﻮان ﻣﺜﺎل ﻋﺒﺎرت «x ﺑﺮ 5 ﺑﺨﺶﭘﺬﻳﺮ اﺳﺖ» ﺑﻪ ازای ﻋﺪد 15 درﺳﺖ و ﺑﻪ ازای ﻋﺪ 3 ﻏﻠﻂ اﺳﺖ.
: ﻣﺤﻤﻞ ﮔﺰاره ای اﺳﺖ درای ﭘﺎراﻣﺘﺮ ﻛﻪ ﺑﻪ ازای ﻣﻘﺎدﻳﺮ ﻣﺨﺘﻠﻔﻲ ﻛﻪ اﻳﻦ ﭘﺎراﻣﺘﺮ ﻣﻲ ﮔﻴﺮد ﻣﻲﺗﻮاﻧﺪ ﮔﺰارهای درﺳﺖ ﻳﺎ 1 ﻣﺤﻤﻮﻻت
ﻧﺎدرﺳﺖ ﺑﺎﺷﺪ. ﻣﺜﻼً اﮔﺮ P ﺑﻪ ﻣﻌﻨﺎی ﺑﺨﺶﭘﺬﻳﺮ ﺑﻮدن ﺑﺎﺷﺪ (P(x,y ﻣﺤﻤﻮل دو ﻣﺘﻐﻴﺮه اﺳﺖ ﻛﻪ ﻣﻲ ﮔﻮﻳﺪ «x ﺑﺮ y ﺑﺨﺶﭘﺬﻳﺮ اﺳﺖ» در
اﻳﻦ ﺻﻮرت p(,) 8 2 درﺳﺖ و p(,) 9 2 ﻧﺎدرﺳﺖ اﺳﺖ.
1 -2-1 2 ﻧﻘﻴﺾ ﻳﺎ ﻧﻔﻲ ﻳﻚ ﮔﺰاره
ارزش ﻳﻚ ﮔﺰاره را ﻣﻌﻜﻮس ﻣﻲﻛﻨﺪ. ﻣﻌﻤﻮﻻً از ﻧﻤﺎدﻫﺎی «» ﻳﺎ «~» ﻳﺎ «Not» ﺑﺮای ﻧﻔﻲ ﻳﻚ ﮔﺰاره اﺳﺘﻔﺎده ﻣﻲﻛﻨﻨﺪ ﺟﺪول درﺳﺘﻲ
آن ﺑﻪ ﺻﻮرت زﻳﺮ اﺳﺖ:
p ~ p
T F
F T
ﻋﻄﻔﻲ ﺗﺮﻛﻴﺐ 2 -2-1 3
ﺗﺮﻛﻴﺐ ﻋﻄﻔﻲ دو ﮔﺰاره دﻟﺨﻮاه p و q ﻛﻪ ﺑﻪ ﺻﻮرت p q ﻧﻤﺎﻳﺶ ﻣﻲدﻫﻨﺪ در ﺻﻮرت درﺳﺖ (T) اﺳﺖ ﻛﻪ ﻫﺮ دو ﮔﺰاره p و q
درﺳﺖ ﺑﺎﺷﻨﺪ و اﮔﺮ ﺣﺪاﻗﻞ ﻳﻜﻲ از آﻧﻬﺎ ﻧﺎدرﺳﺖ ﺑﺎﺷﺪ ﻋﻄﻒ آﻧﻬﺎ ﻧﺎدرﺳﺖ (F) ﻣﻲﺷﻮد.
p q pq
TT T
TF F
F T F
F F F
ﻓﺼﻠﻲ ﺗﺮﻛﻴﺐ 3 -2-1 4
ﺗﺮﻛﻴﺐ ﻓﺼﻞ دو ﮔﺰاره دﻟﺨﻮاه p و q ﻛﻪ ﺑﻪ ﺻﻮرت p q ﻧﻤﺎﻳﺶ ﻣﻲدﻫﻨﺪ در ﺻﻮرﺗﻲ درﺳﺖ (T) اﺳﺖ ﻛﻪ ﺣﺪاﻗﻞ ﻳﻜﻲ از دو ﮔﺰاره
درﺳﺖ ﺑﺎﺷﺪ و در ﺻﻮرﺗﻲ ﻧﺎدرﺳﺖ اﺳﺖ ﻛﻪ ﻫﺮ دو ﮔﺰاره p و q ﻧﺎدرﺳﺖ ﺑﺎﺷﺪ.
p q pq
TT T
TF T
F T T
F F F
ﺷﺮﻃﻲ ﺗﺮﻛﻴﺐ 4 -2-1 5
ﮔﺰاره ﺷﺮﻃﻲ ﺑﻪ ﺻﻮرت p q ﻧﻤﺎﻳﺶ ﻣﻲدﻫﻨﺪ، ﮔﺰاره p را ﻣﻘﺪم و ﮔﺰاره q را ﺗﺎﻟﻲ ﻣﻲﮔﻮﻳﻨﺪ. ﺗﺮﻛﻴﺐ ﺷﺮﻃﻲ p q ﻓﻘﻂ
ﻫﻨﮕﺎﻣﻲ ﻧﺎدرﺳﺖ (F) اﺳﺖ ﻛﻪ ﮔﺰاره ﺳﻤﺖ ﭼﭗ (ﻣﻘﺪم) T و ﮔﺰاره ﺳﻤﺖ راﺳﺖ (ﺗﺎﻟﻲ) F ﺑﺎﺷﺪ. ﮔﺰاره ﺷﺮﻃﻲ را ﭼﻨﻴﻦ ﻣﻲﺧﻮاﻧﻨﺪ:
q آﻧﮕﺎه p اﮔﺮ -1
1
Predicates
2
Negative
3
Conjuction
4
Disjunction
5
Conditional
3
ﺳﺎﺧﺘﻤﺎنﻫﺎی ﮔﺴﺴﺘﻪ / ﻓﺼﻞ اول
p -2 ﺷﺮط ﻛﺎﻓﻲ ﺑﺮای q اﺳﺖ.
q -3 ﺷﺮط ﻻزم ﺑﺮای p اﺳﺖ.
q اﮔﺮ ﻓﻘﻂ p -4
p -5 ﻛﺎﻓﻲ ﺑﺮای q اﺳﺖ.
q -6 ﻻزم ﺑﺮای p اﺳﺖ.
ﺟﺪول درﺳﺘﻲ ﺑﻪ ﺻﻮرت زﻳﺮ اﺳﺖ:
p qp q
TT T
TF F
F T T
F F T
ﺷﺮﻃﻲ دو ﺗﺮﻛﻴﺐ 5 -2-1 1
ﮔﺰاره ﺷﺮﻃﻲ ﺑﻪ ﺻﻮرت p q ﻧﻤﺎﻳﺶ ﻣﻲدﻫﻨﺪ و ﭼﻨﻴﻦ ﻣﻲﺧﻮاﻧﻨﺪ «p اﮔﺮ و ﻓﻘﻂ اﮔﺮ q» ﺗﺮﻛﻴﺐ دو ﺷﺮﻃﻲ p q ﻫﻨﮕﺎﻣﻲ
درﺳﺖ (T) اﺳﺖ ﻛﻪ ﻫﺮ دو ﮔﺰاره p و q ﻫﻢ ارزش ﺑﺎﺷﻨﺪ ﻳﻌﻨﻲ ﻫﺮ دو T ﻳﺎ ﻫﺮ دو F ﺑﺎﺷﻨﺪ. (ﺷﺒﻴﻪ ﮔﻴﺖ XNOR درس ﻣﺪار ﻣﻨﻄﻘﻲ)
p qp q
TT T
TF F
F T F
FF T
ﻧﻜﺘﻪ: ﺗﻘﺪم راﺑﻄﻪﻫﺎی ﻣﻨﻄﻘﻲ ﺑﻪ ﺗﺮﺗﻴﺐ (از ﺑﻴﺸﺘﺮ ﺑﻪ ﻛﻤﺘﺮ) ﻋﺒﺎرﺗﻨﺪ از: ~، ، ، ، در ﺻﻮرت داﺷﺘﻦ
ﭘﺮاﻧﺘﺰ، اوﻟﻮﻳﺖ ﺑﺎ داﺧﻠﻲ ﺗﺮﻳﻦ ﭘﺮاﻧﺘﺰ اﺳﺖ و ﻫﻤﭽﻨﻴﻦ ﺑﻴﻦ راﺑﻂ ﻫﺎی ﻫﻢ اوﻟﻮﻳﺖ ﭼﭗﺗﺮﻳﻦ راﺑﻂ اوﻟﻮﻳﺖ
ﺑﻴﺸﺘﺮ دارد.
3-1 ﺗﺎﺑﻊ ارزش
ﺗﺎﺑﻊ ارزش ﮔﺰاره p ﺑﻪ ﺻﻮرت زﻳﺮ ﺗﻌﺮﻳﻒ ﻣﻲﺷﻮد:
V p( )
1
0
ﺑﺎ اﺳﺘﻔﺎده از (V(p ﻣﻲﺗﻮان راﺑﻂﻫﺎی ﻣﻨﻄﻘﻲ را ﺑﻪ ﺻﻮرت زﻳﺮ ﻧﻴﺰ ﺑﻴﺎن ﻛﺮد:
1) V p Vp (~ ) ( ) 1
2) V p q VqVq ( ) max{ ( ), ( )}
3) V p q V P V q V pV q ( ) min{ ( ), ( )} ( ). ( )
( ) () ( ) ( ) ()