Maths – Propositional Logic

What is Logic?

This is post is going to help you better understand and grasp the concepts behind Propositional Logic (PL). In general, PL is the study  of logical operators and their use in correct arguments.



In this post I am going to be using the logical operators ‘and’, ‘or’, ‘not’, ‘implies’ and ‘iff’ – note, these are also called Boolean operations, as they can only return True or False.

Other import quantifiers that you will need to know, but only later on are ‘for all’ and ‘there exists’.

 

The Operators

As you have probably worked out, you cant really write ‘A and B’ in maths, this doesn't really look very nice, and you most especially can do it in a programming language like Java, C/C++! SO, to denote each operator we need a symbol. These symbols are:

 

Name	Symbol	Translation
negation	¬	not
conjunction	/\	and
disjunction	\/	or
implication	->	implies
bi-implication	<->	iff

 

Note :- i’ve only just realised, but its probably best to note that ‘iff’ means ‘if and only if’, such as A=True iff B=True so A<->B (explained more later…)

 

What the Symbols Do

You’re probably wondering what each of the symbols does right? especially if you’ve never seen them before… Well here we go: :)

• NOT: denoted by ‘¬’. This symbol is used as a prefix, so it comes before the formula it negates. Lets say for example we have the Boolean variable ‘A’, and we say that ‘A’ is False.

   

  
  
  A = False
  
  if we apply the negation operation to ‘A’ we get:
  
  ¬A = True
  
  This is because the opposite of False, is True. If ‘A’ were to initially be True and we applied the negation, then ‘A’ would become False.
  -------------------------------------------------------------------------------------------------


• AND: denoted by ‘/\’. This symbol is used to compare 2 formulas and returns either True or False. for example, if ‘A’ is True and ‘B’ as False, then:A /\ B = False
  
  This is because the AND operator can only return true, if the formulas it is comparing are both True, so A=True and B=True.
  -------------------------------------------------------------------------------------------------


• OR: denoted by ‘\/’. This symbol – again – compares 2 formulas and returns either True or False. However, unlike the AND operator, OR only requires one of the formulas to be True. so unlike the AND, the same A and B would return:A \/ B = True
  
  This is because A is True, so it doesn't mater whether B is True or False.
  -------------------------------------------------------------------------------------------------


• IMPLIES: denoted by ‘->’. This is a complicated one to explain… Basically, it again compares 2 formulas, but it can only return True if ‘A’ is False or ‘B’ is True, or both – such as A and B are True, or A and B are False. So if ‘A’ was True and ‘B’ is False, then it would return False:A –> B = False
  -------------------------------------------------------------------------------------------------


• IFF (BI- IMPLIES): denoted by ‘<->’. This one it fairly straight forward. it can only return True if  ‘A’ and ‘B’ have the same Boolean value. so either A and B both equal True or False. So if ‘A’ si True and ‘B’ is True then:A <-> B = True

Truth Tables

This is the last section in this post. More will be explained in the next one. This post was a quick and brief introduction to the actual operators and symbols themselves.

However, it is now time to look at the operators Truth Table. A truth table is a table that shows all the possible Boolean values for A and B, and then the possible returns from the operators if they were applied to A and B with the given values.

The first one is NOT. for the negation operator we can only apply this to one formula, so:

Note that T=True and F=False

 

A	¬A
T	F
F	T

Next we have the operators AND, OR, IMPLIES and BI-IMPLIES:

A	B	A /\ B	A \/ B	A –> B	A <-> B
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T