Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

4
votes
1answer
185 views

What are those “things that cannot be proved using only ordinary rules of inference”?

The online edition of the book Introduction to Logic by Michael Genesereth and Eric Kao, has a detail that left me confused. CHAPTER 4 [...] 4.2 Linear Proofs [...] The ...
0
votes
1answer
430 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
1
vote
5answers
74 views

If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is ...
0
votes
2answers
3k views

How can I prove [P->(Q->R)] is equivalent to [(P^Q) ->R]

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
2
votes
2answers
208 views

Prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction

I am trying to prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction. Here is my attempt using JAPE application. ...
1
vote
1answer
193 views

A finite set of wffs has an independent equivalent subset

This seems to be a common exercise among many books (cf. Enderton, p. 28, van Dalen, p. 45, Hinman, p. 51, Chang and Keisler, p. 18), with some minor variations among them. The idea is simple. Say ...
2
votes
1answer
58 views

If $\phi$ is satisfiable and $\mathscr{S}$ is countable, then the set of all models of $\phi$ has the cardinality of the continuum

I have just started reading Chang and Keisler and I'm already stuck in an exercise. Let $\mathscr{S}$ be a countable set of sentence letters (i.e. $\mathscr{S} = \{S_0, S_1, S_2, \dots\}$ or some ...
13
votes
1answer
963 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
3
votes
2answers
196 views
1
vote
3answers
138 views

Disjunctive simplification

What is this rule of inference called? $(P\wedge Q)\vee(P\wedge\neg Q)\vdash P$ My (silly) motivation is this answer.
1
vote
2answers
379 views

How to determine whether a set of propositions is consistent?

Definition of consistency is: A set of formulas ⊆ WFF is consistent iff there is no A ∈ WFF such that Σ ⊢ A and Σ ⊢ (¬A). Say you have a set of propositions statements (i.e. $A \lor B \rightarrow C$, ...
-1
votes
2answers
88 views

Convert this solution to inference notation

This is a proof for De Morgan's Law. Could you help me convert this to inference notation so I can understand the proof better? I find it hard reading this, specifically, which line each assumption ...
2
votes
1answer
61 views

Simple Propositional Logic Explaination?

In this example, the prof states that "Q->R doesn't depend on the assumption Q so he can discharge it, but without assumption Q, he couldn't have concluded with Q->R so the answer still depends on the ...
1
vote
2answers
117 views

Use of propositional logic connectives in the meta-language

I have a doubt that might seem a bit confusing so i will try to explain it the clearer i can. Suppose we have an expression "A o B" in the meta-language, where 'o' refers to those logical ...
1
vote
1answer
268 views

Answering questions with truth tables

"With every dinner I have three rules": If I don't drink wine, then I eat soup If I eat soup and drink wine, then I'll have some pudding If I have pudding or don't drink wine, then I'll skip the ...
3
votes
2answers
66 views

Logical implication of the form $P\to P$

Two logical propositions are given. $$P:\ good\ books\ are\ not\ cheap\\ Q:\ cheap\ books\ are\ not\ good$$ Now 3 statements are given: $A:\ P \ implies\ Q\\ B:\ Q\ implies\ P\\ C:\ P\ and\ Q\ are\ ...
2
votes
1answer
177 views

Trouble understanding Lindenbaum's lemma's proof

I'm stuck on the section (b) of the proof of the Lindenbaum's lemma in Geoffrey Hunter's Metalogic (part 32.12). Can't these two derivations ($\Gamma ' \vdash_{PS} A $ and $\Gamma ' \vdash _{PS}\sim A ...
2
votes
1answer
52 views

Help solving a challenge - relational algebra or second order logic

I am a self-taught man and I'm posting my first question here. I'm facing a challenge I'd like to solve. Based on what I know it fits propositional calculus (hope it is). Suppose 3 people: a ...
1
vote
1answer
37 views

semantic equivalence

Hi I am looking to prove that this equivalence holds using rules of semantic equivalence, or if it does not hold give an interpretation that shows it. (p⇒q)∨(r⇒q)≡p⇒(r⇒q) I get ≡implication ...
1
vote
2answers
70 views

prove formulae using natural deduction

Hello I am trying to prove this: ⊢p⇒p∧(p∨q) using natural deduction. p ⊢ p∧(p∨q) p, assumption p ⊢ (p∨q) p, assumption but dont seem to be getting anywhere. can someone please help? thank you. ...
2
votes
1answer
60 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
2
votes
5answers
638 views

truth tables and validity of arguments

$ p $ $ p \to q $ $ \lnot q \lor r$ $ \therefore r$ In order to prove validity with truth tables, do 1) 2) and 3) have to be true in order for the conclusion to be true?
1
vote
1answer
30 views

Is my answer correct for this Logical Analysis of Arguments?

The question is: If U is a subspace of V, then U is a subset of V, U contains the zero vector, and U is closed under addition. U is a subset of V, and if U is closed under addition then U contains ...
1
vote
2answers
28 views

question about equivalence of boolean statements

Does the function $(p \land q) \lor r$ equal the function $p \land (q \lor r)$? please it would be suitable if in your feedback you will include which algebraic rule for boolean function to follow.. ...
7
votes
5answers
236 views

The deep structure of logical formulas

A long-standing question to which I never found a concise answer is: Is there something like an unambiguous deep structure of a formula of propositional logic, opposed to its comparingly ...
0
votes
1answer
135 views

Propositional calculus proof must involve instance of $(\neg \neg p \Rightarrow p )$

Hi this is a question about propositional calculus. The axioms I am working with are: $(p \Rightarrow (q\Rightarrow p))$ $ ((p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q ) ...
5
votes
3answers
371 views

Derive by modus ponens $[A\rightarrow(B\rightarrow C)]\rightarrow[(A\rightarrow B)\rightarrow(A\rightarrow C)]$

How could I derive by modus ponens the formula $$[A\rightarrow(B\rightarrow C)]\rightarrow[(A\rightarrow B)\rightarrow(A\rightarrow C)]$$ from, and just from, the following axiom schemata? $(A\lor ...
1
vote
1answer
337 views

p xor q xor r — simplifying into disjunctive normal form with propositional algebra

So, I have $p \oplus q \oplus r$, and my goal is to simplify into disjunctive normal form with propositional algebra. Step 1: simplyify xor ((($p \wedge \neg q) \vee (\neg p \wedge q)) \wedge \neg ...
1
vote
1answer
311 views

How to prove Lemma 2.12 of Mendelson without Deduction Theorem

My question refers to Bourbaki's axiom system in Nicolas Bourbaki, Théorie des ensembles (1970). [page I.25] : $(P \lor P) \supset P$ --- (Taut) $Q \supset (P \lor Q)$ --- (Add) $(P \lor Q) ...
0
votes
1answer
78 views

Using truth tables to determine logical equivalency

How do you use truth tables to determine whether or not the following pairs of statements are logically equivalent? i) (p ᴧ q)→r ii) p→(q→r) I'm confused on how you would do that, Thanks
2
votes
3answers
35 views

Put $(a \leftrightarrow b) \wedge c$ in DNF

$$(a \leftrightarrow b) \wedge c$$ I'm having problems with this. If I do: $$(a \rightarrow b) \wedge (b \rightarrow a) \wedge c$$ then $$(\neg a \vee b) \wedge (\neg b \vee a) \wedge c$$ But now I'm ...
1
vote
3answers
312 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: For any relations $R,S$ and $T$ of $\mathcal{T}$, the relations ...
1
vote
1answer
28 views

Is it possible to prove an argument is not satiable with equivalences?

I am trying to prove is this argument: (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) is satiable with equivalence. Is what I said below valid for this? (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) q ∨ (p ∧ ¬p) ...
0
votes
1answer
425 views

Propositional Logic with rules of inference problem.

$$ \begin{array}{l} 1.\>\>\>\> (r ∧ ¬s) ∨ (q ∧ ¬s)\\ 2.\>\>\>\> ¬s → ((p ∧ r) → u)\\ 3.\>\>\>\> u → (s ∧ ¬t)\\ ...
0
votes
1answer
68 views

Rules of Inference…From the following premises, conclude that p → q.

1. (r ∧ ¬s) ∨ (q ∧ ¬s) 2. ¬s → ((p ∧ r) → u) 3. u → (s ∧ ¬t) ----------------------- Prove from the previous arguments. p → q Hey guys, I am really lost, so far I ...
1
vote
1answer
60 views

Equivalence Proof (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r).

I am trying to prove (p ∧ q) ∨ ¬(p → q) ∨ ¬(q ∧ r) ≡ ¬r ∨ (q → p). So far I have done the following: (p ∧ q) ∨ ¬(¬p ∨ q) ∨ ¬(q ∧ r) Implication Definition (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬q ∨ ¬r) De ...
1
vote
2answers
114 views

not p whenever q — do i understand this?

The phrase is not p whenever q. I take this to mean the same thing as not p if q. When p is false, q can be true or false. When p is true, q is false. When q is true, p is false. When q is false, p ...
1
vote
1answer
54 views

Name for DNF simplification rule / prime implicants under closure?

I was reading this question which links to this list of propositional equivalences. One of the equivalences shown (T5a) is: $$ A \wedge B \vee A \wedge \neg B \equiv A $$ I have used this rule by ...
0
votes
4answers
133 views

Proving a proposition is a tautology

I have to prove $P \lor ( Q$ XOR $R) \lor (R \rightarrow Q)$ is always true. I got $P \lor ( R \rightarrow \lnot Q ) \lor (R \rightarrow Q)$. Now I'm stuck at this part. I have no idea how to ...
0
votes
1answer
74 views

Propositional Calculus basic rules

I've been learning propositional calculus and proofs and I'm not sure if we are able to write $(P \lor Q) \leftrightarrow (\lnot P \rightarrow Q)$. If I am doing a proof will i be able to replace (P v ...
4
votes
3answers
171 views

A question about Implicational Propositional Calculus

My question is motivated by a previous post about Implicational calculus Having showed that Mendelson (A1) and (A2) axioms plus Peirce's law are a complete axiom set for implicational fragment of ...
2
votes
3answers
843 views

Deduction Theorem + Modus Ponens + What = Implicational Propositional Calculus?

Implicational propositional calculus is a system of propositional calculus in which implication is the only logical connective, and all other connectives are defined with respect implication and a ...
0
votes
2answers
55 views

If “If $A$, then $B$ and not $C$” is true, then is “If $A$ and $C$, then not $B$” true?

Suppose "If $A$, then $B$ and not $C$" is true. Is the following statement true? If $A$ and $C$, then not $B$. I know the answer is true but I don't know the basis behind it.
2
votes
1answer
81 views

How to solve Distributivity of $\lor$ over $\land$

The problem I need to prove is $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ I am trying to get the RHS equivalent to the LHS So I change $(p \lor q) \land (p \lor r)$ (using the Golden ...
0
votes
2answers
79 views

Curry-Howard isomorphism for disjunction elimination

I am trying to find out how the disjunction elimination rule of natural deduction relates to the Curry-Howard isomorphism. The rule: $P \vee Q, P \Rightarrow C, Q \Rightarrow C \vdash C$ I have been ...
1
vote
2answers
110 views

Circuit Logic NAND

I have to build a circuit using only NAND gates. But I wasn't given an equation. Instead I was given this formula: F(wxyz)= E m(0,1,2,3,4,5,7,14,15) Function of (wxyz) = Sum m(0,1,2,3,4,5,7,14,15) ...
0
votes
1answer
82 views

Confusion in Conjunctive normal forms

Which of the Following is TRUE about formulae in Conjunctive Normal form? For any formula, there is a truth assignment for which at least half the clauses evaluate true. For any formula, there is a ...
1
vote
2answers
78 views

How is this disjunctive form found through propositional algebra

I'm learning about disjunctive normal form and the algebra of propositions. The text is Discrete Mathematics with Graph Theory, 3rd Edition by Goodaire and Parmenter (it wasn't highly recommended on ...
4
votes
1answer
127 views

How to derive this equivalence in propositional logic

This is a homework assignment from a discrete math class that I never took - it asks how to prove the statement $\neg \neg p \equiv p$. The catch is that only the following equivalences can be used: ...
1
vote
1answer
39 views

Logical Proposition simplification

I'm Trying to simplify this: $$ [(¬p \vee ¬q)\to¬(r \vee s)] \wedge ¬s \wedge r$$ so far, I got into this: $$ [(p \wedge q) \vee (¬r \wedge ¬s)] \wedge r \wedge ¬s$$