Logic and Modelling – Propositional Logic

OK, first things first. I am only doing these LaM notes because i’ve been begged to do them :P

Since a lot of Propositional Logic is extremely basic, then I am going to be quick a brief on these notes. However, do note that they are slightly more advanced than what you learnt in previous years, like here: Year 1 PL

So, with this, lets get down to the nitty gritty :D

 

Get Your Priorities Straight!

All connectives in PL have a priority, and knowing these come in very handy when trying to split up a formula for trees, or try to convert them into CNF or DNF.

Firstly, they’re 2 more connectives I need to introduce, they are: T and _|_ (please note that that last symbol is suppose to be an upside-down ‘T’):

 

T	True – Latin: Verum
_|_	False – Latin: Falsum

 

Here’s a list of priorities for all the connectives:

 

Name	Connective	Priority
Verum	T	0
Falsum	_|_	0
Negation	¬	1
Conjunction	/\	2
Disjunction	\/	2
Implies	=>	3
Bi-implies (Equivalence)	<=>	4

 

These priorities are very helpful. For example, say we have a formula:

• p /\ q => r

Now, does this say ‘p /\ (q => r)’ or ‘(p /\ q) => r’?

Well, if we use the priorities above, we see that /\ has a higher priority than =>, so we need to place brackets around that sub-formula first. So this leaves us with the answer of the latter solution:

• (p /\ q) => r

 

Interpretations

I’ll admit, when i first saw this, for like the next 5 weeks I was like “wtf is that I()??”, eventually I understood what it was, and to be honest, it seems pretty pointless…

Don’t threat though, its uber simple. For example, take ‘T’ (varum). This implies True, yes? and in binary, what is always true? exactly, a ‘1’. So the interpretation that satisfies ‘T’ is: ‘I(T) = 1’

All the rest are really simple:

• I(T) = 1
• I(_|_) = 0
• I(A /\ … /\ An) = 1    if and only if I(Ai) = 1 for all Ai
• I(A \/ … \/ An) = 1    if and only if I(Ai) = 1 for some Ai
• I(¬A) = 1     if and only if I(A) = 0
• I(A => B) = 1     if and only if I(A) = 0 or I(B) = 1
• I(A <=> B) = 1     if and only if I(A) = I(B)

Well, thats all im doing on the further advancements of PL. If you would really like me to do more, then please tell me :P