Theory of Logic

Back to Discrete Mathematics
Arjit Sharma
02 Mins

Logic is the backbone of programming, testing, and systems design. Discrete math formalizes logic so we can reason clearly like turning “maybes” into “provable truths”.

Propositional Logic

A proposition is a statement that’s either true or false.

Example - “It is raining”, “I am happy” ., etc all these statements (predicate) can be either true or false.

Logic operators

SymbolMeaningCondition
¬pNOTReverse true to false and vice cersa.
p∧qANDResults true if both are true
p∨qORResults true if either is true
p→qIMPLIESIf p is true, then q must be true
p↔qBICONDITIONALTrue if p and q have the same truth value

Truth Tables

These are your cheatsheet showing all possible outcomes from a proposition.

Example - Let A = “It is sunny” and B = “I have money”. Then lets make a truth table for

logic

A (sunny)B (have money)Buy ice-cream
truetruetrue
truefalsefalse
falsetruefalse
falsefalsefalse

Then we can look at our truth table and identify suitable combinations from the table. In this case we know a similar result as buying a ice cream, is achievable by And operator (A And B)

Code Example

if (isAdmin && isActive) {
    allowAccess();
}

Its nothing but a proposition logic (isAdmin ∧ isActive → access) in form of a code.

First Order Predicate Logic

Goes beyond simple statements and lets us talk about variables. FOL extends simpler systems by allowing automated reasoning systems to apply rules to entire categories of objects without needing to list every single one individually.

first-order-predicate-logic

Quantifiers

Quantifiers are used to express statements about collections of objects. They are binding operators that determine the scope of variables over a specified domain. There are 2 types of Quantifiers -

quantifiers

  • Universal Quantifier - ∀x (“for all x”) ∀x (x² ≥ 0) This is read as “For all x, x squared is greater than equal to 0”
  • Existential Quantifier - ∃x (“there exists an x”) ∃x (x² = 4) This is read as “There exists an x, where x squared equals 4”

This is the basis of assertions in formal verification, tests, and proofs.

Code Example

SELECT * FROM products 
WHERE EXISTS (
    SELECT * FROM inventory 
    WHERE inventory.quantity = 0
);

example-of-predicate-logic

It shows that is there atleast one product out of stock (Existential)

Conclusion

Logic helps you write code that makes sense and prove that it works the way it should. No guesses anymore !

Next →