CS205M Quiz #1

Questions and Answers

Which of the following is a well-formed propositional formula?

(p ∧ q) → (q ∨ r)

¬(p → (q ∧ p)) (correct)

p → (q ∧ ¬p)

p ∨ (q ∨ p¬r)

If p → q is false, what can be inferred about the truth values of p and q?

p is true and q is false. (correct)

Both p and q are true.

Both p and q are false.

p is false and q is true.

How would you formalize the statement: 'Only one among Amit, Bimal, and Chandra passed the exam'?

A ∧ ¬B ∧ ¬C

(A ∧ ¬B) ∨ (B ∧ ¬C) ∨ (C ∧ ¬A) (correct)

A ∨ B ∨ C

(A ∨ B) ∧ ¬(A ∧ B) ∧ ¬C

What is the required conclusion for the formal proof: (p ∧ (p → q) ∧ (s ∨ r) ∧ (r → ¬q)) → (s ∨ t)?

At least one of s or t is true. Signup and view all the answers

How can the proposition (p(0, 0) ∨ p(0, 1)) ∧ (p(1, 0) ∨ p(1, 1)) be represented by a quantified expression?

∃x[p(x, 0) ∨ p(x, 1)] Signup and view all the answers

What free variable exists in the well-formed formula ∀x(p(x) → ∃y¬q(f(x), y, f(y)))?

f(x) Signup and view all the answers

Which of the following expressions contains free variables?

¬∀x(p(x) → ∃y¬q(x, y)) Signup and view all the answers

What does the well-formed formula ∀x∃y p(x, f(y)) → q(x, y) imply?

For every x, there exists a y such that p holds, leading to q. Signup and view all the answers

Study Notes

Quiz Format and Submission Instructions

Answers must be on blank sheets and in the order of the questions.
Convert responses into a single PDF file for submission.
File naming convention: RollNo-Q1.pdf (e.g., 200109009-Q1.pdf).
Include name and roll number at the top of each page.
Maximum of three pages allowed for answers.
Collaboration is prohibited and will incur penalties.

Quiz Structure

Total Questions: 8
Maximum Marks: 40
Time Limit: 40 Minutes

Propositional Logic Questions

Well-formed Propositional Formulas:
- Identify which formulas among given options are correctly structured.
Truth Value Evaluation:
- Analyze the truth value of the expression (¬p ∧ q) ↔ (p ∨ q) when p → q is false.

Propositions and Formalization

Propositions for Students:
- Define propositions: A (Amit passed), B (Bimal passed), C (Chandra passed).
Sentence Formalization:
- Formalize "only one passed" using logical notation.
- Formalize "exactly two passed" using propositional logic.

Formal Proof

Required Proof:
- Prove the implication (p ∧ (p → q) ∧ (s ∨ r) ∧ (r → ¬q)) → (s ∨ t).

Predicate Logic and Quantification

Predicate Representation:
- Represent the proposition (p(0, 0)∨p(0, 1))∧(p(1, 0)∨p(1, 1)) using quantifiers based on the domain D = {0, 1}.
Identifying Free Variables:
- Analyze well-formed formulas (wffs) to find any free variables in different logical expressions.

WFF Interpretation

Translation to English:
- Write an English interpretation of specific well-formed formulas provided in the quiz.

Description

Test your knowledge with Quiz #1 for CS205M, covering key concepts and topics from the course. Make sure to follow the submission guidelines carefully, including formatting your answers and naming your PDF file based on your roll number.