Fundamentals of Computer Science - Week 1 Summary - Part 1 out of 2

1.1 Propositional logic

What is propositional logic?

It's a system that deals with propositions or statements.

What is a proposition? What is a statement?

Proposition is a statement that can be either true or false. It must be one or the other. Cannot be both.

Examples:

2 is a prime number // true
5 is an even number // false

Examples of sentences that are not propositions

* Sentences whose truth value depends on variables are not propositions.
* Questions and imperatives are not propositions.

X is a prime number // can't tell since it can be both as we don't know X
Are you going to school? // cannot assign a truth value because it's a sentence
Do your homework // sentence is an order. has no truth value

Notations of propositional logic

* Propositions are denoted by CAPITAL letters, P, Q, S, ...
  * P = carrots are orange
  * Q = I went to a party yesterday

* General statements are denoted by lowercae letters, p, q, ...
  * unspecified truth values are also called propositional variables

We can use connectives to change or combine the meanings of propositions.

See https://en.wikipedia.org/wiki/List_of_logic_symbols

* Logical NOT (also called negation) ¬
  * ¬p is true if and only if p is false.
* Logical OR (also called disjunction) ∨
  * p ∨ q is true if one of them is true.
* Logical AND (also called conjunction) ∧
  * p ∧ q is true if both of them are true.
* Logical IF...THEN (also called conditional or implication) →
  * p → q where p is the premise and q is the conclusion
  * p → q is true if and only if either p is fale or q is true
* Logical IF and only IF ↔
  p ↔ q is true if and only if both p and q are true
* Exclusive OR: XOR ⊕
  * p ⊕ q is true if p or q is true but not both

Truth table: example

* Truth table is a set of all possible outcomes of propositions and connectives.
* The number of rows in a truth table depends on the number of given propositions. If we have n propositions in our formula, our truth table will have 2^n.

Basic Connectives
* Negation: can be thought as one minus the truth value of p
* Conjunction: will give a true truth value when both propositions are true. Mathematically think of it as multiplication. T(p) x T(q).
* Disjunction: will be true if at least one of the propositions is true (can be thought as maximum of p and q)
* Conditional or implication: Think of implication as a promise. For example, if you study hard, then I will give you a cookie. I only break this promise if you actually study hard and I don't give you the promised cookie. Otherwise, I have not broken this promise. So if you don't study and I decide to give you the cookie, this connective is a still true.Mathematically, think of it as less than or equal to p then q is the same as p is less than or equal to q.

Other connectives
* bi-conditional: will be true when p and q have the same truth value. You can think of it as an equality check.
* Exclusive OR: will be true if only one of p or q is true. It's the opposite of bi-conditional

Operator precedence for propositional logic

¬ ∧∨ → ↔

1.2 Tautology and consistency

Tautology

* A formula that output is always true no matter the truth values of the propositions
* Not all formula is a tautology
* Example: p∨¬p
  * (p∧q)→p
  * (p∧q)→q

Consistent

* A formula that is true at least for one scenario
* Example: p∧q
* All the connectives are consistent

Not consistent

* Not consistent or inconsistent is a formula that is never true
* It's also called contradiction
* Example: p∧¬p, (p∧¬p) (p∧¬p)

Essencial reading

Rosen, K.H. Discrete mathematics and its applications (New York: McGraw-Hill, 2012) 7th edition, Chapter 1.1-1.2, pp.1-22.

Comments

Popular posts from this blog

syllabus: Algorithms and Data Structures 1 [CM1035]

syllabus: Fundamentals of Computer Science [CM1025]

Introduction to Programming - Week 1 and 2 Summary