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
Advertisements

About Badgerati
Computer Scientist, Games Developer, and DevOps Engineer. Fantasy and Sci-fi book lover, also founder of Cadaeic Studios.

One Response to Maths – Propositional Logic

  1. Pingback: Year 2 – Logic and Modelling – Propositional Logic « Computer Science: Source

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: