گسسته2

V p Vq Vp q V p Vq

 

  

 

1

0 4)

 ( ) () ( ) ( ) ()

V p Vq Vp q V p Vq

    

 

1

0 5)

1

 Biconditional

اﮔﺮ p درﺳﺖ ﺑﺎﺷﺪ

اﮔﺮ p ﻏﻠﻂ ﺑﺎﺷﺪ

اﮔﺮ

اﮔﺮ

اﮔﺮ

اﮔﺮ 

 4

 ﺳﺎﺧﺘﻤﺎنﻫﺎی ﮔﺴﺴﺘﻪ / ﻓﺼﻞ اول

 ﺗﻌﺎرﻳﻒ 4-1

 1 -4-1 1 ﻓﺮﻣﻮل ﮔﺰارهای ﻫﻤﻴﺸﻪ درﺳﺖ

ﮔﺰاره ﻣﺮﻛﺒﻲ ﻛﻪ ﻣﺴﺘﻘﻞ از ارزش ﮔﺰاره ﻫﺎی ﻣﻌﻴﻨﻲ ﻛﻪ ﺟﺎﻳﮕﺰﻳﻦ ﭘﺎراﻣﺘﺮﻫﺎی آن ﻣﻲﺷﻮد دارای ارزش درﺳﺖ ﺑﺎﺷﺪ، ﻓﺮﻣﻮل ﮔﺰارهای 

ﻫﻤﻴﺸﻪ درﺳﺖ ﻣﻲﮔﻮﻳﻨﺪ.

ﻣﺜﺎل: ﻋﺒﺎرتﻫﺎی p  p و ~ q q  ﻫﻤﻴﺸﻪ درﺳﺖ ﻫﺴﺘﻨﺪ.

 2 -4-1 2 ﻓﺮﻣﻮل ﮔﺰارهای ﻫﻤﻴﺸﻪ دروغ

ﻓﺮﻣﻮل ﮔﺰارهای ﻛﻪ ﻣﺴﺘﻘﻞ از ارزش ﮔﺰاره ﻫﺎی ﻣﻌﻴﻨﻲ ﻛﻪ ﺟﺎﻳﮕﺰﻳﻦ ﭘﺎراﻣﺘﺮﻫﺎی آن ﻣﻲ ﺷﻮﻧﺪ ارزش ﻧﺎدرﺳﺖ داﺷﺘﻪ ﺑﺎﺷﺪ را ﻓﺮﻣﻮل

 ﮔﺰارهای ﻫﻤﻴﺸﻪ دروغ ﻣﻲﮔﻮﻳﻨﺪ.

ﻣﺜﺎل: ﻋﺒﺎرت p ~ p ﻓﺮﻣﻮل ﮔﺰارهای ﻫﻤﻴﺸﻪ دروغ اﺳﺖ.

ﺟﺎﻳﮕﺰﻳﻨﻲ ﻧﻤﻮﻧﻪ 3 -4-1 3

ﮔﻮﻳﻴﻢ ﻓﺮﻣﻮل A ﻳﻚ ﻧﻤﻮﻧﻪ ﺟﺎﻳﮕﺰﻳﻨﻲ از ﻓﺮﻣﻮل B اﺳﺖ ﻫﺮﮔﺎه ﺑﺘﻮان ﻓﺮﻣﻮل A را ﺑﺎ ﺟﺎﻳﮕﻴﻦ ﻧﻤﻮدن ﮔﺰارهﻫﺎﻳﻲ ﺑﻪ ﺟﺎی ﺑﺮﺧﻲ ﮔﺰاره ﻫﺎی

ﻓﺮﻣﻮل B ﺑﻪ دﺳﺖ آورد.

 ﻧﻜﺘﻪ: ﺟﺎﻳﮕﺰﻳﻨﻲ ﻓﻘﻂ ﺑﺮای ﻣﺘﻐﻴﺮﻫﺎی ﮔﺰاره ای اﻧﺠﺎم ﻣﻲﮔﻴﺮد، ﺑﻪ ﻋﻨﻮان ﻣﺜﺎل ﻋﺒﺎرت p ~q ﻣﻲﺗﻮان ﻋﺒﺎرت

r s  ( ) را ﺟﺎﻳﮕﺰﻳﻦ q ﻛﺮد وﻟﻲ ﻧﻤﻲﺗﻮان ﺟﺎﻳﮕﺰﻳﻦ q~ ﻛﺮد.

 ﻧﻜﺘﻪ: در ﻳﻚ ﻋﺒﺎرت ﺷﺎﻣﻞ ﺑﻴﺶ از ﻳﻚ ﻣﺘﻐﻴﺮ ﻳﻜﺴﺎن، ﻋﻤﻞ ﺟﺎﻳﮕﺰﻳﻨﻲ ﺑﻪ ﻃﻮر ﻫﻤﺰﻣﺎن اﻧﺠﺎم ﻣﻲﮔﻴﺮد.

 5-1 4 ﻓﺮﻣﻮل ﻫﺎی ﺧﻮش ﺳﺎﺧﺖ

ﻓﺮﻣﻮل ﺧﻮش ﺳﺎﺧﺖ ﺑﻪ ﺻﻮرت زﻳﺮ ﺗﻌﺮﻳﻒ ﻣﻲﺷﻮد:

1- ﻳﻚ ﮔﺰاره ﻧﻤﺎ ﺑﻪ ﺗﻨﻬﺎﻳﻲ WFF اﺳﺖ.

2- اﮔﺮ A ﻳﻚ WFF ﺑﺎﺷﺪ، آﻧﮕﺎه A~ ﻧﻴﺰ ﻳﻚ WFF اﺳﺖ.

 .اﺳﺖ WFF ﻧﻴﺰ A BA BA BA B  , ,,  آﻧﮕﺎه ﺑﺎﺷﻨﺪ WFF دو ﻫﺮ B و A اﮔﺮ -3

4- ﺑﻪ ﺻﻮرت ﺑﺎزﮔﺸﺘﻲ ﺑﺎ ﺗﻜﺮار ﻗﻮاﻧﻴﻦ 1 و 2 و 3 رﺷﺘﻪ WFF ﭘﺪﻳﺪ ﻣﻲآﻳﺪ.

 .اﺳﺖ WFF ﻳﻚ p   ( ) q r ﻋﺒﺎرت وﻟﻲ ﻧﻴﺴﺖ WFF ﻳﻚ ( ) ()   p q r ﻋﺒﺎرت :ﻣﺜﺎل

ﻣﺜﺎل: ﺑﺎ ﺟﺎﻳﮕﺰﻳﻦ ﻧﻤﻮدن p ﺑﺎ q و p q (~ ) ﺑﺎ p در ﻋﺒﺎرت p  q qp ( )( ) ﻧﻤﻮﻧﻪ ﺟﺎﻳﮕﺰﻳﻨﻲ را ﺑﻪدﺳﺖ آورﻳﺪ:

 ( ( (~ )) ( ( ~ )) p     q p qq p (2 (( ) ( ~ )) ( ( ~ )) p   p q qp q (1

 (( ( ~ )) ( (( ) ~ )) q pq qq p    (4 ( ( ~ )) ( ( ~ )) q p q pp q    (3

 ﺣﻞ: ﮔﺰﻳﻨﻪ «3»

 ﺑﻨﺎ ﺑﺮ ﺗﻌﺮﻳﻒ ﻓﺮﻣﻮل ﺧﻮش ﺳﺎﺧﺖ در ﺑﺎﻻ ﮔﺰﻳﻨﻪﻫﻴﺎ (2) ،(1) و (4) ﻏﻂ ﻫﺴﺘﻨﺪ.

6-1 ﻫﻢ ارزی

دو ﮔﺰاره A و B ﻫﻢارزﻧﺪ اﮔﺮ ﺑﻪ ازای ﻫﺮ ﻳﻚ از ﺗﺮﻛﻴﺒﺎت ارزش ﻣﻤﻜﻦ ﺑﺮای ﻣﺘﻐﻴﺮﻫﺎﻳﺸﺎن، ارزش ﻳﻜﺴﺎﻧﻲ داﺷﺘﻪ ﺑﺎﺷﻨﺪ و ﺑﻪ ﺻﻮرت

A BA B   ( ) ﻧﻤﺎﻳﺶ ﻣﻲدﻫﻴﻢ. ﺑﻪ ﻋﻨﻮان ﻣﺜﺎل p  p ﺑﺎ p ﻫﻢ ارز اﺳﺖ.

1

 Tautology

2

 Contradiction

3

 Substitution Instance

4

 Well formed formula (WFF) 

 5

ﺳﺎﺧﺘﻤﺎنﻫﺎی ﮔﺴﺴﺘﻪ / ﻓﺼﻞ اول

ﺑﺮای ﺗﺸﺨﻴﺺ ﻫﻢارزی دو ﮔﺰاره A و B ﻣﻲﺗﻮان از ﻃﺮق زﻳﺮ اﺳﺘﻔﺎده ﻛﺮد:

1- ﺑﺎ اﺳﺘﻔﺎده از ﺟﺪول درﺳﺘﻲ و ﻣﻘﺎﻳﺴﻪ ﺳﺘﻮن آﺧﺮ آﻧﻬﺎ ﻛﻪ ﺑﺎﻳﺪ ﻳﻜﺴﺎن ﺑﺎﺷﺪ.

2- ﺑﺎ اﺳﺘﻔﺎده از ﮔﺰاره دو ﺷﺮﻃﻲ A B  ﻛﻪ ﺑﺎﻳﺪ ﻳﻚ ﺑﺎﺷﺪ.

 ﻧﻜﺘﻪ: اﮔﺮ A و B ﻫﻢارز ﺑﺎﺷﻨﺪ ﺗﺮﻛﻴﺐ دو ﺷﺮﻃﻲ A B ﻫﻤﻮاره درﺳﺖ اﺳﺖ.

 .اﺳﺖ A C آﻧﮕﺎه B CA B ,  اﮔﺮ :ﻧﻜﺘﻪ 

ﺟﺪول زﻳﺮ ﻫﻢ ارزیﻫﺎی ﻣﻬﻢ را ﻧﺸﺎن ﻣﻲدﻫﺪ:

ﻧﺎم ﻗﺎﻧﻮن ﮔﺰاره

ﺧﻮد ﺗﻮاﻧﻲ (

)

p p p

p p p

 

 

1

2

ﺟﺎﺑﺠﺎﻳﻲ (

)

p q qp

p q qp





1

2

( ) ( )( ﺷﺮﻛﺖﭘﺬﻳﺮی

)( ) ( )

p q r p qr

p q r p qr

   

   

1

2

( )( ) ( ) ( ﺗﻮزﻳﻊﭘﺬﻳﺮی ـ ﭘﺨﺸﻲ

) ( ) ( )( )