Tuesday, 22 March 2011

Propositional logic and De Morgan's Law

Starting from now till April 6th. I will most likely be posting blogs relating to what i am doing in school. Using writing my blogs as one of the many forms i will use to study for my final exams. Now i have three final exams. One for my major(computer science), and two relating to my math classes. Discrete, and Calculus.
 //Covering (Sec 1.1 - 1.2). personal note
Propositional Logic:

what is a proposition?

A proposition is a statement that is either true or false.
Ex. This is a propositional statement.

Now that we got that covered you can do logic with propostions using logical operators.

Logical Operators:

where NOT is denoted by ~, implication is denoted by ->, AND is denoted by ^, OR is denoted by V,
 Exclusive OR denoted by ⊕, biconditional denoted by <->.

NOT works as a negation. If the propostion p was true. The negation of p denoted ~p would  be false.
 Implication  works as the following. If p then q. Now what this means is if p is true then q is true. Now this also works for if q is true then p must also be true. This is helpful if you have the propostional statement.

If p then dogs can bark. Well we know nothing about the statement p, but since p implies q. We know that q is true therefore p must also be true.

AND works as the following. P^Q. P is true and Q is false then the statement is not true.  P and Q are false the statement is not true. P is false and Q is true the statement is false. The only way a statement with the AND operator is true is if both P and Q are true.

OR works similar to AND. P V Q is true if either P or Q is true. The only time the statement can be false is if both P and Q are false.

Exclusive OR works a bit differently then OR. P V Q is true if only one of P or Q is true. So this proposition can only be false by having both of P and Q false, or both P and Q being true.

 Biconditional works as the opposite of the Exclusive OR. P<-> Q is only true. If both P and Q are true, or both P and Q are false.

Some examples:

Let p, q, r be the propositions:
p: you have the flu
q: you miss the final exam
r: you pass the course

Express P->Q (p implies q).

If you have the flu, then you miss the final exam.

Express Q-> ~R (Q implies the negation of R)

If you miss the final exam, then you do not pass the course.

Express (P-> ~R) V (Q -> ~R) (p implies the negation of R) or (Q implies the negation of R)

If you have the flu, then you do not pass the course or if you miss the final exam, then you do not pass the course.

Now what is the logical operator equation of:

If dogs can fly, then grass is green.

If you answered P -> Q, you were correct. 

Truth Tables:

A truth table is a nice way of keeping track of how a logical operator equation outcomes.

To create a truth table for an equation. You take the propositions.  Denote them by a letter, usually P, Q,R,....Z

Then you create a column on the far left as the following exmaple shows.

 P  ||  Q| Passing each different outcome for P and Q or how every many propositions used.
--------| These outcomes T and False are called Truth Values.
T  ||   T |
T  ||   F |
F  ||   T |
F  ||   F |

So lets make a truth table for  [(P->Q)^(~P)]

 P  ||  Q| ( P -> Q) | ~P  | [ (P -> Q) ^ (~P) ] 
T  ||   T |      T        |   F  |               F
T  ||   F |      F        |   F  |               F
F  ||   T |      T        |   T  |               T

F  ||   F |      F        |   T  |               F

So that is how a truth table works it is great for when you are trying to show that two logical equations are logically equivalent.

 Such as by looking at ( P -> Q) ^ ( P -> R) is equivalent to P -> (Q ^ R)

Now by looking at these two equations you may be able to see that they are equivalent. But for the most part creating a truth table can show and prove that these two are equivalent.


Tautology: A compound proposition that is always true for all truth values.
Contradiction: A compound proposition that is always false for all truth values.

De Morgans Law:
is the way in which the negation of a compound proposition can be rewritten as another equivalent compound proposition.


p -> Q equivalent ~P V Q
P -> Q equivalent  ~P - > ~Q
P V Q equivalent ~P -> Q

~(PVQ) equivalent ~P ^ ~Q



  1. Ha Logic... That's where all started... Nowadays I do Temporal Logic but I remember when I was doing logic in high school ^^

  2. great formula; keep up the good work :)

  3. ah logic, I remember doing huge truth tables only to be told there was a short cut weeks later haha

  4. Logic hurts my brain when you write it :P


  5. Looks so complex to me, and I guess it's so easy to you guys. :p You make the programs and let me find the bugs for you then. ;)

  6. Man this stuff used to keep me up at night when I took Philosophy. I have it down like the back of my hand though!

  7. condition and logic is very core to programming, thanks for the tips!

  8. very interesting. still seems like another language to me, but very cool haha

  9. I took a class on this last semester

  10. I remember truth tables...This way of thinking goes hand in hand with programming.

  11. I was lost after the first couple of sentences haha.