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)

1
vote
1answer
42 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 ...
0
votes
1answer
132 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
34 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
31 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
196 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
23 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
64 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
43 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
41 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
33 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
49 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
57 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 ...
2
votes
2answers
74 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
2answers
196 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
55 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
56 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
85 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
40 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
57 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
74 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
30 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
34 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
56 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?
0
votes
6answers
131 views

Logic - Is $A \rightarrow ( B \rightarrow C) $ equivalent to $A \rightarrow C$?

I know that $A \rightarrow B$ and $B \rightarrow C$ resolves to $A \rightarrow C$ but does $A \rightarrow (B \rightarrow C)$ also resolve to $A \rightarrow C$?
1
vote
3answers
36 views

How to read parens

How do you read the parentheses in this proposition? That is, what do you say in English when reading from the end of a parenthesis to the next? Are the parens simply read as "such that"? $ ( ∀ x ∈ Z ...
1
vote
6answers
107 views

Determine if tautology, contingency or contradiction

I have to determine if the statement is a tautology, contradiction or contingency. Been at it for days but didn't get too far. The original question is $$\left((\lnot p\vee z)\wedge(p\vee ...
0
votes
2answers
34 views

Intro to Discrete Structures $\;\lnot A \rightarrow (A \rightarrow B)$

Im trying to use propositional logic to break this down but i have no clue. i know about the rule that if a wff ends in form ....implies (a implies b), the a can be ...
0
votes
2answers
60 views

$(A \lor B) \land C \iff (A \lor C) \land (B \lor C)$?

Assume $A$, $B$, and $C$ are three independent predicates. Maybe $A$ stands for "my age is 20," and $B$ "stands for tomorrow is a good day." So is it true that $(A \lor B) \land C \iff (A \lor C) ...
0
votes
1answer
22 views

Using the resolution method in logic

Using the resolution method in logic, having these clauses $$\{ \neg M \vee S, \neg S \vee T, \neg W \vee T, W \vee M, \neg T, \neg T \vee S \}$$ is it possible to reach the contradiction directly ...
1
vote
2answers
58 views

How can I show that three statements are not logically equivalent to another?

I am given three premises and a conclusion. The premises are: \begin{gather} p \lor q \\ p \to \mathord{\sim}q \\ p \to r \end{gather} and the conclusion is $$ r $$ I used a truth table and showed ...
-2
votes
1answer
55 views

Propositional Logic use of simplification?

Can I use Simplification when it's not the only logical connective in a proof? For example: $(P \wedge Q) \Longrightarrow C$ premise $P \Longrightarrow C$ Simp. 1 $ Q \Longrightarrow ...
0
votes
4answers
55 views

Symmetric difference equality

Something I was thinking about earlier: If $A\triangle B=A \triangle C$, does $B=C$? Where $\triangle$ is symmetric difference. My intuition is telling me no, but I can't seem to think of an example ...
-3
votes
1answer
57 views

Boolean algebra help please!

Let $a, b$ be any elements in a Boolean algebra. Prove that the following statements are equivalent: a) $a = ab$ b) $ab^{'}=0$ c) $a^{'}+ b = 1 $ [Hint: Show the following chain of implications: ...
1
vote
2answers
90 views

First-order logic: how-to produce interpretation where a given formula is false?

For example, given Theory T with predicates $$A(x), B(x), C(x,y), D(x,y), x=y$$ axioms $$\exists x.A(x) \land \exists x.B(x) \land \exists xy.C(x,y)\\ \forall x(A(x) \leftrightarrow \neg B(x)),$$ ...
0
votes
0answers
31 views

Generalized distributive law

Let $p,q,r,C_{ij}$ be formulae in propositional logic, or even simply symbols, i'm only interested in notations. Distributive law says: $$p\vee (q\wedge r)=(p\vee q)\wedge (p\vee r)$$ I want to ...
3
votes
6answers
108 views

Show that $\neg(p \Longleftrightarrow q)$ and $p \Longleftrightarrow \neg q$ are logically equivalent

Given there are 2 logical variables $p$, $q$ . Show that $\neg(p \Longleftrightarrow q)$ and $p \Longleftrightarrow \neg q$ are logically equivalent without using the truth table. And here is my ...
1
vote
0answers
47 views

Propisitional logic exam questions and answers

I'm going over exam questions, since my exam is hours away. I'd be extremely grateful if you could check out my answers and evaluate them. Hopefully you guys can see the truth table. Also, i have ...
2
votes
0answers
36 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
1answer
58 views

Are my answers for these propositional calculus questions right?

Formalize the following English sentences as propositional logic formulas: $i)\quad$ "When the front and back doors are closed then the light is off." $ii)\quad$ "Either the lift doors are open or ...
0
votes
2answers
69 views

Where do the brackets go in $p \wedge q \vee \neg p \rightarrow \neg q$?

I have been give the following question for homework: Let $p$ be the statement "She will graduate" and let $q$ be "She will find a job". Then what would be: "Either she will graduate and find ...
1
vote
0answers
58 views

Propositional logic truth tables

For the exam that I am taking, propositional always comes up with identical questions. These include writing a sentences in propositional logic, which I can do. But also drawing a truth table for ...
4
votes
5answers
145 views

Are $p \to (q \to r)$ and $p \to (q \wedge r)$ logically equivalent?

Is $p \to (q \to r)$ logically equivalent to $p \to (q \wedge r)$? I simplified each one, I got $\neg\, p \vee(q \vee r)$ and $\neg\, p ∨(\neg\, q \wedge r)$ respectively. Not sure if my ...
0
votes
1answer
48 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
2
votes
1answer
103 views

How to check the validity of this argument using the rules of inference?

I have this argument : I play basketball and football. If today isn't Saturday, then I play basketball and football. If today is Friday OR today is Saturday, then I don't play football. Therefore, ...
6
votes
2answers
181 views

Is this a valid proposition?

Consider following two sentences. $x^2 = 1.$ Today is Thursday. The first statement can't be a proposition. because the truth of (1) depends on the value of $x$. For some values of $x$ it is true ...
1
vote
1answer
42 views

Mathematical logic question propsitional logic

"When the front and back door are closed then the light is off" p - "front" q - "light is off" r - "back doors are closed" $$(p\land r) \rightarrow q$$ Would this be logically correct?
2
votes
4answers
384 views

Satisfiability Problem: Determining Which People To Invite

When planning a party you want to know whom to invite. Among the people you would like to invite are three touchy friends. You know that if Jasmine attends, she will become unhappy if Samir is ...
4
votes
7answers
202 views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
0
votes
1answer
20 views

Are all substitution-closed sets schematic?

I assume everyone is familiar with propositional logic and its language. Let $S$ be a set of wffs of propositional logic. The set $S$ is said to be substitution-closed iff whenever $x$ is in $S$, ...
0
votes
0answers
19 views

Weighted partial MaxSAT (and MinSAT) with real-valued weights?

Consider the following optimization problem ($\min$-version also of interest): $$ \max_{β\in\{0,1\}^m}\{c'φ(β): ψ(β)=1\} = \max_{\phi\in\{0,1\}^n}\{c'\phi: β\in\{0,1\}^m, \phi=φ(β), ψ(β)=1\},$$ ...