Proposition

1 .Proposition Logic

Proposition is a statement that tells a fact despite of its exactness

Example:

He is Pang Kok An

He is pregnant.

1 + 1 = 2

2 + 3 = 6

The above examples are examples of propositions. The first statement states the fact that the person in the picture is Pang Kok An. It’s a true statements, therefore it’s a propositions. 

The second statement states that he is pregnant. General knowledge tells us that a man cannot be pregnant. Therefore, although it’s false but still be considered as a proposition because the statement had told a fact, although it’s a wrong fact.

Statement 3 tells the fact that 1 + 1 = 2. Therefore it’s a proposition. The same goes to Statement 4.

Let’s see some examples:

 Do you like peanuts?

 Please listen carefully!

 x + 1 = 2

 x + y = z

Statement 1 asks you do you like peanuts. You can say the sentence is neither true nor false. That is because you can determine its exactness since it doesn’t tell any fact. The same goes to Statement 2. Statement 2 does not tell you the fact but it’s a sentence that shows up a request.

x + 1 = 2 is also nor true nor false. If you put 1 as x, it would be true. But if you put

2 as x, the statement would turn wrong. Same goes to Statement 4.

The statements which are neither true nor false are not propositions.

Propositional variable

We have learnt before that a variable is something that represents a value.  

x = 2

The statement above shows that the variable x is representing the number 2.

A propositional variable is a variable which represents a proposition.

For example:

x = My lecturer is Madam Elissa

y = She is still singled.

The above example shows that variable x is representing the proposition “My lecturer is Madam Elissa” whereas the variable y represents the proposition “She is still singled”.

Truth Value

A true proposition has a truth value of T, whereas a false proposition has a truth value of  F. 

Negation

A negation to the proposition statement is what makes a positive proposition into negative and vice versa.

Example 1:

x = My lecturer is Madam Elissa

Turn this proposition into a negative statement and you will get:

¬x = My lecturer is not Madam Elissa/Madam Elissa is not my lecturer.

The symbol ¬ means not. Therefore ¬x means not x.

Example 2:

y = She is still singled.

¬y = She is not singled. / She is married.

x	¬x
T	F
F	T

Table above shows truth table for negation

Connective operators

Connective operators are used to connect two or more propositions and thus produce a new proposition. There are many types of connective operators.

AND operator

Connective operator “and” connects two propositions that will become a true compound proposition only if two of them are true.

Example:

x = My lecturer is Madam Elissa  

y = She is married.

There are 2 propositions. We use “and” to connect these 2 propositions and it will become

x ∧ y = My lecturer is Madam Elissa and she is married.

Note that the symbol ∧ represents the operator “and”.

In order to have the compound proposition true, the two propositions  must be true.

x	y	x ∧ y
T	T	T
T	F	F
F	T	F
F	F	F

Truth table for operator ∧

OR operator

Connective operator “or” connects two propositions that will become a true compound proposition if at least one of two of them are true.

Example:

x = She may have an egg

y = She may have a cup of coffee

There are 2 propositions. We use “or” to connect these 2 propositions and it will become

x ∨ y = She may have an egg or a cup of coffee.

Note that the symbol ∨ represents the operator “or”.

In order to have the compound proposition true, the two propositions  must be true.

x	y	x ∨ y
T	T	T
T	F	T
F	T	T
F	F	F

Truth table for operator ∨

Exclusive-OR operator

Connective operator “exclusive-or” connects two propositions that will become a true compound proposition if only one of two of them are true.

Example:

x = Those who take Akidah dan Akhlak in Sem 2 have registered their courses correctly.

y = Those who take Moral dan Etika in Sem 2 have registered their courses correctly.

x ⊕ y = For those who take Akidah dan  Akhlak or Moral dan Etika, BUT NOT BOTH have registered their courses correctly.

Note that the symbol ⊕ represents the operator “or”.

In order to have the compound proposition true, only one of the two propositions  must be true.

x	y	x ⊕ y
T	T	F
T	F	T
F	T	T
F	F	F

Truth table for operator ⊕

Conditional Statement

Conditional statement connects two proposition, one of them is the hypothesis part and the other one is the conclusion part. 

Example 1:

x = You are an IT student.

y = you must be familiar enough with computers.

Let x to be the hypothesis part and y as the conclusion part. Then it should be look like this:

x → y = If you are an IT student, you must be familiar enough with computers.

Note that the symbol → represents if…..then, so in this case, x → y means if x, then y.

The above statement is true. IT students must be familiar with computers.  

Example 2:

¬x →¬y = If you are not an IT student, you may not be familiar enough with computers.

The above statement is true. Non-IT students are not familiar with computers. 

Example 3:

¬x →y = If you are not an IT student, you may be familiar enough with computers.

The above statement is true. Some non-IT students are familiar with computers. 

Example 4:

x →¬y = If you are an IT student, you must not be familiar enough with computers.

The above statement is unreasonable. IT students have no reason why they are unfamiliar with computers.

All the results are true except for compound propositions with true hypothesis and false conclusion.

x	y	x ∨ y
T	T	T
T	F	F
F	T	T
F	F	T

Truth table for conditional statement

Biconditional Statement

Biconditional statement is denoted with double-arrow sign ↔. x ↔ y means x if and only if y.

Example 1:

x = It is not going to rain.

y = There are no grey clouds

1.  x ↔ y = It is not going to rain if and only if there are no grey clouds.

2. ¬x →¬y = It is not going to rain if and only if there are no grey clouds.

3. ¬x →y = It is not going to rain if and only if there are grey clouds.

4. ¬x →¬y =It is not going to rain if and only if there are no grey clouds.

Statement 1 and 4 are reasonable. Statement 2 and 3 are not reasonable because in order to rain, it needs grey clouds.

From the example above, you can see that if biconditional statement is true if two propositions are of same truth value.

x	y	x ∨ y
T	T	T
T	F	F
F	T	F
F	F	T

Truth table for biconditional statement

 2.Proposition Equivalance

Tautology

A compound proposition that is always true.

Contradiction

A compound proposition that is always false

Contingency

A compound proposition that is neither a tautology nor a contradiction.

Logical Equivalences

Compound proposition that have the same truth values in all possible cases. Means, compound propositions p and q are called logically equivalent if p ↔ q is a tautology.

Example of Tautology and Contradiction

p	q	p∨ -p	p ∧ -p
T	T	T	F
F	F	T	F

*p ∨-q is always true

*p ∧-q is always false

Logical equivalences tables

Name	Equivalence
Identity Laws	p ∧ T ≡ p p ∨ F ≡ p
Domination Laws	p ∨ T ≡ T p ∧ F ≡ F
Idempotent Laws	p ∨ p ≡ p p ∧ p ≡ p
Negation Laws	p ∨¬p ≡ T p ∧¬p ≡ F
Double Negation Law	¬(¬p) ≡ p
Commutative Law	p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p
Absorption Law	p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
De Morgan’s Laws	¬(p ∧ q) ≡¬p ∨¬q ¬(p ∨ q) ≡¬p ∧¬q
Associative Laws	(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive laws	p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

*T = Compound proposition is always true

*F = Compound proposition is always false

Logical Equivalences involving Conditional Statements

p → q ≡ ¬p ∨ q

p → q ≡ ¬q →¬p

p ∨ q ≡¬p → q

p ∧ q ≡¬(p →¬q)

¬(p → q) ≡ p ∧¬q

(p → q) ∧ (p → r) ≡ p → (q ∧ r)

(p → r) ∨ (q → r) ≡ (p ∧ q) → r

(p → q) ∨ (p → r) ≡ p → (q ∨ r)

(p → q) ∧ (p → r) ≡ p → (q ∧ r)

  

Logical Equivalences involving Biconditional Statements

p ↔ q ≡ ¬p ↔¬q

¬(p ↔ q) ≡ p ↔¬q

p ↔ q ≡ (p ∧ q) ∨ (¬p ∧¬q)

p ↔ q ≡ (p → q) ∧ (q → p)

Example Logical Equivalent.

Shows that are logical equivalents.

Double Negation Law ¬(¬p) ≡ p

p	-p	-(-p)
T	F	T
F	T	F

Commutative Law p ∨ q ≡ q ∨ p

p	q	p ∨ q	q ∨ p
T	T	T	T
T	F	T	T
F	T	T	T
F	F	F	F

Associative Law (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

p	q	r	(p ∨ q)	(p ∨ q) ∨ r	(q ∨ r)	p ∨ (q ∨ r)
T	T	T	T	T	T	T
T	T	F	T	T	T	T
T	T	T	T	T	T	T
T	T	F	T	T	F	T
F	F	T	T	T	T	T
F	F	F	T	T	T	T
F	F	T	F	T	T	T
F	F	F	F	F	F	F

Example Logical Equivalent involving Conditional Statement

Shows that are logical equivalents.

¬(p → q) ≡ p ∧¬q

p	q	¬(p → q)	¬q	p ∧¬q
T	T	F	F	F
T	F	T	T	T
F	T	F	F	F
F	F	F	T	F

(p → q) ∨ (p → r) ≡ p → (q ∨ r)

p	q	r	(p → q)	(p → r)	(p → q) ∨ (p → r)	(q ∨ r)	p → (q ∨ r)
T	T	T	T	T	T	T	T
T	T	F	T	F	T	T	T
T	F	T	F	T	T	T	T
T	F	F	F	F	F	F	F
F	T	T	T	T	T	T	T
F	T	F	T	T	T	T	T
F	F	T	T	T	T	T	T
F	F	F	T	T	T	F	T

Example Logical Equivalent involving Biconditional Statement

p ↔ q ≡ (p → q) ∧ (q → p)

p	q	p ↔ q	p → q	q → p	(p → q) ∧ (q → p)
T	T	T	T	T	T
T	F	F	F	T	F
F	T	F	T	F	F
F	F	T	T	T	T

3. Predicates and Quantifiers

Predicates

x + 1 = 2

x + y = z

x > 5

Student x had failed the exam.

These statements are neither true nor false before we substitute x with other definite numbers or values. We are going to look at how to produce propositions from these above statements.

Let’s look at the example below:

Student x had failed the exam.

This statement consists of 2 parts. The first part is “Student x”, which we call it as variable. And the second part, which is “had failed the exam” is the predicate part.

We can denote this statement with P(x), in which x is the variable and P is the predicate. P(x) means “The propositional function P with value x” or “The propositional function P at x”

Let’s see some examples to help you understand better.

Example 1:

x + 1 = 2

Let the above statement be denoted with P(x), what is the truth value of P(1) and P(4)?

Answer:

when x = 1,

P(1) : 1 + 1 = 2 (True)

when x = 1,

P(4) : 4 + 1 = 2 (False)

Example 2:

The ID, x is valid.

Every account’s ID is distinct from each other. Therefore, when two users sign up using the same ID, the ID is valid for the first user but invalid for the second user.

At first, a user named Kenny had signed up by using number 3 as his ID. Now you want to sign up for a new ID.

Let the above statement be denoted with P(x), what is the truth value if you put number 4 as your ID and also number 3?

Answer:

when number 4 is used as your ID,

P(4) : 4 ≠ 3(True)

Therefore, the ID is valid.

when number 3 is used as your ID,

P(3) : 3 = 3(True)

Therefore, the ID is invalid. 

Preconditions and Postconditions

The idea of predicates is often applied in the field of computer science. Programmers and developers make various programs and use predicates on detecting any possible errors that may occur.

For example,

Below is a simple program to calculate what is the increment of the value a user will input.

x = x + 1

A precondition is what we think the valid input for the statement is. For example, we are going to test the program by inputting number 1. Therefore, we can say that the precondition for this statement or program is 1.

P(1) : x = 1

A postcondition is what we think the valid output for the statement should look like. Since we have assume number 1 as the precondition, we’ll expect that the output should be number 2. Therefore, we can say that the postcondition for this statement or program is 2.

P(2) : x = 2

2 = 1 + 1

Quantifiers

Quantifiers are used to determine whether a statement is valid if the input variables have meet certain conditions.

There are 2 types of quantifiers. Universal quantifier and existential quantifier.

Universal quantifier

Universal quantification of P(x) means P(x) for all values of x in the domain. If P(x) is true with condition all the value of x in the domain must be true, then we can say that for all values of x P(x) is true, or we can use the notation:

∀ x P(x) is true

where ∀ represents “for all”.

We can express universal quantification of P(x) like this:

x₁ ∧ x₂ ∧ x₃ ∧ …… ∧ x_n

Example 1:

P(x) : x + 1 < x + 2

From the above statement, we can see that no matter what is the value of x, x + 1 will definitely be smaller than x + 2. Therefore we can say for all values of x P(x) is true, or ∀ x  P(x) is true

Example 2:

P(x) : x > 3

From the above statement, we can see that not all value of x can suit this statement. For example, when x = 4, the statement is true but when x = 2, the statement will be wrong. It is only true for some values of x. Therefore we can say for all values of x P(x) is false, or ∀ x  P(x) is false

Existential quantifier

Existential quantification of P(x) means P(x) for some values of x in the domain. If P(x) is true with condition at least one of the x values in the domain must be true, then we can say that for some values of x P(x) is true, or we can use the notation:

∃ x P(x) is true

where ∃ represents “for some”.

We can express universal quantification of P(x) like this:

x₁ ∨ x₂ ∨ x₃ ∨ …… ∨ x_n

Example 1:

P(x) : x > 3

From the above statement, we can see that some value of x can suit this statement. For example, when x = 4, the statement is true. It is true for some values of x. Therefore we can say for some values of x P(x) is true, or ∃ x  P(x) is false

Example 2:

P(x) : x + 1 > x + 2

From the above statement, we can see that no matter what is the value of x, x + 1 will not be greater than x + 2. Therefore we can say for some values of x P(x) is false, or ∃ x  P(x) is false. 

Uniqueness quantifier

Uniqueness quantification of P(x) means P(x) for only a specific value of x in the domain. If P(x) is true with condition only a specific value of x in the domain, then we can say that for only a specific value of x P(x) is true, or we can use the notation:

∃! x P(x) is true

or

∃₁ x P(x) is true

where ∃! or ∃₁  represents “for only”.

We can express uniqueness quantification of P(x) like this:

P(x) = x_s  , where x_s  denotes the specific value of x.

Example 1:

P(x) : x + 2 = 3

From the above statement, we can see that this statement only suits one value, that is x = 1. If we put other value instead of 1 as the value of x, the statement will become false. It is only true for x = 1. Therefore we can say for a specific value of x P(x) is true, or ∃! x  P(x) is true

Example 2:

P(x) : x > 3

From the above statement, we can see some values of x can suit this statement. There are more than one value of x which make this statement true. Therefore, it is not only true for some values of x but true for some values of x. Therefore we can say for a specific value of x P(x) is false, or ∃! x  P(x) is false

Quantifiers in reality

Example 1:

You are assigned by your lecturer to create an enrolment system for the his course portal. The enrolment system will stop once all your coursemates have enrolled theirselves into the course

We can ensure that which students have enrolled themselves into the course by making this statement:

P(x) = Student x had enrolled himself/herself into the course.

Let say a student named Ali had enrolled himself into the course while Abu had not. We can say that the statement:

P(Ali) = Ali had enrolled himself/herself into the course.

is true whereas:

P(Abu) = Abu had enrolled himself/herself into the course.

is false.

Let say there are 30 students in your class. So you have to program your enrolment system in which it will stop after all of the students had enrolled. We can determine it using the statement below:

x₁ ∧ x₂ ∧ x₃ ∧ …… ∧ x₃₀

The enrolment system will just continue running until ∀ x  P(x) is true.

Example 2 :

There are 10 food stalls in the cafeteria.

If 10 of them are open, many students will go and buy their food there. If only 1 of them are open, students will still go there and buy their food, but the number of students is lesser. When do students not go there and buy their food? If none of them are open, there will be no students who is still willing to go there.

From the above statements, we can make a simple statement to determine whether the selected stall is open or not.

Q(x) = Stall x is open.

Let say stall 10 is open and the rest of them are close. So:

Q(10) = Stall 10 is open.

is true while

Q(2) = Stall 2 is open.

is false.

If there is at least one stall which is open, there wil be students going there. So we can write like this below:

x₁ ∨ x₂ ∨ x₃ ∨ …… ∨ x₁₀

There will be students going to the café if ∃ x  P(x) is false

Example 3:

Three students, Alex, Dexter and Robert are assigned to be working in a group for their assignments. A good teamwork and cooperation is badly needed in a team.

They have different characteristics.

Alex can become a good leader. He is good at giving precise commands and work very efficient in his team.

Dexter is a hardworking student. He do things fast. He likes to ensure any overlooked works before the deadline of submitting.

Robert, on the other hand is quite a lazy student. Even he is assigned to jobs and assignments, he always likes to do it in the last minute.

In order to make teamworks efficient, a leader must be chosen among them to increase efficiency.

P(x) = x is the leader.

We all know that Alex is a good leader. So definitely the value of x is Alex and not Robert or Dexter. Therefore we can say that Alex is the only person who is eligible to become a leader of the group, or in the mathematical terms there exists a unique x such that P(x) is true.

Our slide on chapter 1:
https://doc-0g-bc-docs.googleusercontent.com/docs/securesc/qj9hdibv4bf8i64gm1a8hskjlae3h5dq/9oa22pbc3uqp65aifkh5h8ns1cdogei8/1362024000000/06042155070242527045/06042155070242527045/0BzGLj71LFdH0VVNCSm5rakRoQ00?e=download