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
138 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
83 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
69 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
92 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
99 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. ...
0
votes
1answer
61 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
43 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 ...
11
votes
1answer
924 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
116 views
1
vote
3answers
64 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
125 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$, ...
0
votes
2answers
61 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
51 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
78 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
95 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 ...
2
votes
1answer
81 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
49 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
25 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
52 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. ...
1
vote
1answer
47 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
194 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
28 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
24 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.. ...
6
votes
5answers
196 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
108 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 ) ...
0
votes
0answers
37 views

Translate n xor expressions to CNF?

I have n xor expressions: a xor b xor c xor d... I want to translate to cnf: The answer of cnf can be found here: http://www.wolframalpha.com/input/?i=a++XOR+b++XOR+c+XOR+d+ I want to write a ...
5
votes
3answers
307 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
50 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
172 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
47 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
33 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
2answers
228 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: $(R\lor R)\Rightarrow R$. $R\Rightarrow (R\lor S)$. $(R\lor ...
1
vote
1answer
24 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
105 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
58 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
45 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
1answer
41 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
54 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
61 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 ...
3
votes
3answers
108 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
356 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 ...
1
vote
1answer
66 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
60 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
88 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
44 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
60 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 ...
3
votes
1answer
78 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
33 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$$
0
votes
2answers
37 views

Logical Equivalence with →

I am given the problem of proving: $p → (q\land r) \equiv (p→q) \land(p→r)$ Using known logical equivalences. I'm not well practiced in transforming logical statements that contain →'s in them into ...
0
votes
2answers
89 views

Propositional Logic, P or Q but not both.

If I had two propositions, P and Q, and wanted to write an expression such that either P or Q are true but not both, what would be the best notation for it?