Discrete Math Logical Equivalence

Image for post
Biconditional Truth Table [1] Brett Berry

Logical equivalence is a type of relationship between two statements or sentences in propositional logic or Boolean algebra.

You can’t get very far in logic without talking about propositional logic also known as propositional calculus.

A proposition is a declarative sentence (a sentence that declares a fact) that is either true or false.

Examples of propositions:

  1. Tallahassee is the capital of Florida
  2. Washington D.C. is not the capital of the United States
  3. 0 + 2 = 2
  4. 2 + 3 = 10

Propositions 1 and 3 are true, while propositions 2 and 4 are false, not both true and false.

We use letters to denote propositional variables, similar to how letters can represent numbers. The conventional letters used are p,q,r,s,….. The truth value of a proposition is denoted by T and false value by F.

Truth Table

Let’s take a look at some other Truth Tables. The below tables show the comparison of True and False being represented in binary as 1 and 0.

Image for post
Truth Table for Logical Negation in TF and 01 notations [1] by Brett Berry
Image for post
Logical False (aka always false) in TF and 01 notations[1] by Brett Berry

Tautology

[ (p → q ) ^ p ] → q = T

Contradiction

If you want to read up on more logic and proposition problems or Discrete Math topics in general a great book to easily learn and practice these topics is Practice Problems in Discrete Mathematics by Bojana Obrenic’, and Discrete Math Workbook: Interactive Exercises by James R. bush.

Image for post
Image for post
Practice Problems in Discrete Mathematics by Bojana Obrenic’
Image for post
Image for post
Discrete Math Workbook: Interactive Exercises by James R. bush

Check Out the following for content / videos on Algorithm Analysis, Programming and Logic:

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

RESOURCES:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store