Unit 2: Logic Calculus - Subjective Questions
MTH136 — Discrete Structures • Practice Questions with Detailed Answers
20 questions
Define a proposition in logic. Give two examples of statements that are propositions and two that are not.
A proposition is a declarative statement that is either true or false, but not both. It has a definite truth value.
Examples of propositions:
- "The sum of and is ." (True)
- "Paris is the capital of Germany." (False)
Statements that are NOT propositions:
- "What time is it?" (a question, has no truth value)
- "Please close the door." (a command/request)
- "" (an open sentence whose truth depends on )
Key point: Only statements that can be definitively classified as true or false qualify as propositions.
Explain the difference between a simple (atomic) proposition and a compound proposition with suitable examples.
Simple (Atomic) Proposition:
- A proposition that cannot be broken down into smaller propositions.
- It does not contain any logical connectives.
- Example: : "It is raining."
Compound Proposition:
- A proposition formed by combining one or more simple propositions using logical connectives such as (AND), (OR), (NOT), (implies), (if and only if).
- Example: : "It is raining and it is cold."
Comparison Table:
| Feature | Simple | Compound |
|---|---|---|
| Connectives | None | One or more |
| Divisibility | Indivisible | Divisible into simpler parts |
| Example | "The sky is blue" | "The sky is blue and the sun is shining" |
Conclusion: Compound propositions are built from atomic propositions using logical operators, and their truth values depend on the truth values of the components.
Describe the three basic logical operations: conjunction, disjunction, and negation. Provide their symbols and truth tables.
1. Conjunction ( — AND):
- is true only when both and are true.
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
2. Disjunction ( — OR):
- is true when at least one of or is true (inclusive OR).
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
3. Negation ( — NOT):
- reverses the truth value of .
| T | F |
| F | T |
Summary: These three operations form the foundation of propositional logic and can be used to build all other compound statements.
Construct the truth table for the compound proposition .
We evaluate the proposition step by step for all combinations of , , .
| T | T | T | T | F | T |
| T | T | F | T | T | T |
| T | F | T | F | F | F |
| T | F | F | F | T | T |
| F | T | T | F | F | F |
| F | T | F | F | T | T |
| F | F | T | F | F | F |
| F | F | F | F | T | T |
Explanation:
- First compute (true only when both are true).
- Then compute (negation of ).
- Finally take the disjunction of these two columns.
The final column gives the truth value of the entire expression for each combination.
Define tautology and contradiction. Show, using truth tables, that is a tautology and is a contradiction.
Tautology: A compound proposition that is always true regardless of the truth values of its components.
Contradiction: A compound proposition that is always false regardless of the truth values of its components.
Truth table for (Tautology):
| T | F | T |
| F | T | T |
Since the last column is always T, is a tautology (Law of Excluded Middle).
Truth table for (Contradiction):
| T | F | F |
| F | T | F |
Since the last column is always F, is a contradiction (Law of Contradiction).
Define logical equivalence. Prove that (De Morgan's Law) using a truth table.
Logical Equivalence: Two compound propositions are said to be logically equivalent (denoted ) if they have the same truth values for all possible combinations of their component propositions. Equivalently, their biconditional is a tautology.
Proof of :
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
Conclusion: The columns for and are identical. Therefore, they are logically equivalent, proving De Morgan's Law.
Explain the conditional statement (). Discuss its truth table, and define its converse, inverse, and contrapositive.
Conditional Statement (): Read as "if then ". Here is the hypothesis (antecedent) and is the conclusion (consequent). It is false only when is true and is false.
Truth Table:
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Related Conditionals (for ):
- Converse:
- Inverse:
- Contrapositive:
Important equivalences:
- A conditional is logically equivalent to its contrapositive:
- The converse is equivalent to the inverse:
Define the biconditional statement (). Construct its truth table and explain when it is true.
Biconditional Statement (): Read as " if and only if " (abbreviated as "iff"). It represents that and have the same truth value.
Truth Table:
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
When is it true?
- is true when both and are true, or both are false (they share the same truth value).
- It is false when they have different truth values.
Key equivalence:
This shows the biconditional combines a conditional and its converse.
Distinguish between the inclusive OR and exclusive OR (XOR) operations with their truth tables.
Inclusive OR ():
- is true if at least one of or is true (including when both are true).
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Exclusive OR ( / XOR):
- is true if exactly one of or is true (but not both).
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Key Difference:
- The only difference is in the first row (both true): inclusive OR gives T, exclusive OR gives F.
- Everyday language example: "You may have coffee or tea" (XOR — pick one), versus "Students with a laptop or tablet may register" (inclusive — either or both).
Using a truth table, verify whether the following compound proposition is a tautology, contradiction, or contingency: .
We evaluate both sides and their biconditional.
| T | T | T | F | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Observation: The final column is always True.
Conclusion: The proposition is a TAUTOLOGY. This also proves the important equivalence:
A contingency would have a mix of T and F, and a contradiction would be all F — neither applies here.
State and prove the Distributive Laws of propositional logic using truth tables.
The Distributive Laws are:
Proof of Law 1:
| T | T | T | T | T | T | T | T |
| T | T | F | T | T | T | F | T |
| T | F | T | T | T | F | T | T |
| T | F | F | F | F | F | F | F |
| F | T | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | F | F | F | F | F | F | F |
Conclusion: Columns for and are identical, proving Law 1. Law 2 can be proven similarly by duality.
Explain the terms antecedent and consequent. Symbolize the statement: "If it rains, then the ground gets wet" and write its contrapositive, converse, and inverse in words.
Antecedent: The hypothesis part of a conditional statement — the part following "if". In , is the antecedent.
Consequent: The conclusion part — the part following "then". In , is the consequent.
Symbolization:
- Let : "It rains" and : "The ground gets wet".
- Statement:
Related forms in words:
- Converse (): "If the ground gets wet, then it rains."
- Inverse (): "If it does not rain, then the ground does not get wet."
- Contrapositive (): "If the ground does not get wet, then it does not rain."
Note: The original statement and its contrapositive are logically equivalent, and the converse and inverse are logically equivalent to each other.
Prove the Absorption Laws: (a) and (b) using truth tables.
Absorption Laws simplify expressions where a variable is absorbed.
(a) :
| T | T | T | T |
| T | F | F | T |
| F | T | F | F |
| F | F | F | F |
The column matches column . ✔
(b) :
| T | T | T | T |
| T | F | T | T |
| F | T | T | F |
| F | F | F | F |
The column matches column . ✔
Conclusion: Both laws hold as their result columns are identical to the column.
Using truth tables, show that the conditional statement is logically equivalent to its contrapositive , but NOT to its converse .
Truth table comparison:
| T | T | T | F | F | T | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | F |
| F | F | T | T | T | T | T |
Analysis:
- Conditional vs Contrapositive: Columns and are identical → they are logically equivalent. ✔
- Conditional vs Converse: Columns and differ in rows 2 and 3 → they are NOT equivalent. ✘
Conclusion: A conditional always equals its contrapositive but generally not its converse.
Define logical connectives and list the common connectives used in propositional logic with their symbols and meanings.
Logical Connectives: These are symbols or words used to combine one or more propositions to form compound propositions. The truth value of the compound proposition depends on the truth values of the component propositions and the connectives used.
Common Logical Connectives:
| Connective | Symbol | Name | Meaning |
|---|---|---|---|
| Negation | NOT | Reverses truth value | |
| Conjunction | AND | True if both are true | |
| Disjunction | OR | True if at least one is true | |
| Exclusive OR | XOR | True if exactly one is true | |
| Conditional | IMPLIES | False only if antecedent T, consequent F | |
| Biconditional | IFF | True if both have same truth value |
Order of precedence (highest to lowest): , , , , .
Example: is interpreted as .
Prove that is a tautology (Law of Syllogism) using a truth table.
This proves the Hypothetical Syllogism rule of inference.
| Full Expression | |||||||
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
Observation: The final column (the full implication) is always True.
Conclusion: The proposition is a TAUTOLOGY, confirming the validity of the Law of Syllogism: if and , then .
State the fundamental laws (algebra) of propositional logic such as Identity, Idempotent, Complement, and Double Negation laws.
The Laws of Propositional Algebra (where T = tautology, F = contradiction):
1. Idempotent Laws:
2. Identity Laws:
3. Domination (Null) Laws:
4. Complement (Negation) Laws:
- (Excluded Middle)
- (Contradiction)
5. Double Negation Law:
6. Commutative Laws:
7. Associative Laws:
8. De Morgan's Laws:
These laws are used to simplify and manipulate logical expressions.
Simplify the compound proposition using the laws of logic and state the result.
We simplify step by step using logical laws.
Given:
Step 1 — Apply De Morgan's Law to :
Step 2 — Apply Double Negation ():
Step 3 — Substitute back into the full expression:
Step 4 — Apply Idempotent Law ():
Result:
The expression simplifies to , which is true only when is true and is false.
Compare tautology, contradiction, and contingency. Give one example of each.
These three terms classify compound propositions based on their truth values across all combinations.
Comparison Table:
| Type | Definition | Truth Values |
|---|---|---|
| Tautology | Always true for every combination | All T |
| Contradiction | Always false for every combination | All F |
| Contingency | Sometimes true, sometimes false | Mix of T and F |
Examples:
1. Tautology:
| T | F | T |
| F | T | T |
2. Contradiction:
| T | F | F |
| F | T | F |
3. Contingency:
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Conclusion: A contingency's truth depends on the input, unlike tautologies (always true) and contradictions (always false).
Symbolize the following statements using logical connectives and given propositions, then explain each: (i) "John is intelligent but not hardworking." (ii) "If John studies then he will pass, and if he does not study then he will fail."
Let us define the propositions:
- : "John is intelligent"
- : "John is hardworking"
- : "John studies"
- : "John will pass"
(i) "John is intelligent but not hardworking."
- The word "but" acts as a conjunction (AND).
- "not hardworking" is the negation of .
- Symbolic form:
- Explanation: This is true only when John is intelligent ( = T) and he is not hardworking ( = T, i.e., = F).
(ii) "If John studies then he will pass, and if he does not study then he will fail."
- "If studies then pass":
- "If does not study then fail":
- Joined by "and": conjunction.
- Symbolic form:
- Explanation: This compound statement combines two conditionals. Interestingly, it is logically equivalent to the biconditional ("John passes if and only if he studies"), since it asserts studying and passing always occur together.
Define a proposition in logic. Give two examples of statements that are propositions and two that are not.
A proposition is a declarative statement that is either true or false, but not both. It has a definite truth value.
Examples of propositions:
- "The sum of and is ." (True)
- "Paris is the capital of Germany." (False)
Statements that are NOT propositions:
- "What time is it?" (a question, has no truth value)
- "Please close the door." (a command/request)
- "" (an open sentence whose truth depends on )
Key point: Only statements that can be definitively classified as true or false qualify as propositions.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill. The rest comes out of a student's own pocket: the domain, the storage, and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason. to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it. What it pays for →