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)

3
votes
2answers
59 views

Proof, is $\lnot p \land \lnot q \vdash p \iff q$?

I have derived the proof to some extent, mentioned below:- $$\begin{array}{rll} 1. &\lnot p \land \lnot q &\text{Premise} \\ 2. &\lnot p ...
2
votes
2answers
115 views

Is “It is raining or it is not raining.” a tautology?

Is the following proposition a tautology: "It is raining or it is not raining." I is obviously always true, so one thinks that it should be a tautology. However, i thought a tautology has free ...
3
votes
3answers
136 views

If $B$ is a model for the set of positive consequences of $\Gamma$, then there's $A \subseteq B$ such that $A \models \Gamma$

I'm working through Chang & Keisler again and got stuck on the following exercise (1.2.14) about propositional logic. First, consider a set $\mathscr{S}$ of sentence symbols of arbitrary ...
1
vote
1answer
97 views

Easy question on Logic and Modes Ponens

I got confused with these: using ONLY this three axioms and Modus Ponens:$$1. \ F \implies (G\implies F) \\ 2. \ (F \implies (G\implies H))\implies ((F \implies G)\implies (F \implies H)) \\ 3. \ ...
2
votes
4answers
215 views

The Order of Mixed Quantifiers

How can we derive the implication: $$ ∃y∀xP(x,y) \implies ∀x∃yP(x,y) $$ In other words, when quantifiers in the same sentence are of the same type (all universal or all existential), the order in ...
-1
votes
1answer
69 views

Proving a Tautology Formally [closed]

I wish to prove: $(\neg p\leftrightarrow q)\leftrightarrow\neg(p\leftrightarrow q)$
0
votes
2answers
31 views

Does $r \implies \neg q$, $q$ give $\neg r$?

In resolution, if we have a premise such as $r \implies \neg q$ and we know that $q$ is true, can we infer $\neg r$? If yes what is the rule called
1
vote
1answer
39 views

Semantic tableau software

Is it possible to find software to perform semantic tableaus (as described in http://en.wikipedia.org/wiki/Method_of_analytic_tableaux) automatically? Right now I am proofing it by hand.
1
vote
1answer
70 views

Simplification problem with discrete mathematics

I am trying to achieve this equation: $$x_1x_4 \lor x_1x_2x_3\lor (¬x_1)x_3(¬x_4)$$ I start with: $$(x_1 \lor (¬x_4))(x_3\lor x_4)((¬x_1)\lor x_2\lor x_4)$$ Then I do simplify in the following ...
2
votes
1answer
62 views

Prove formula's tautology

Prove that a formula that only consists of variables, logical negation and logical equality, and in which all variables and negation appear for an even number of times, must be tautological.
0
votes
1answer
52 views

Solution of a symbolic logic problem with Separation of Cases inference rule

$$(( S \land \lnot P ) \lor ( Q \land R )) ∴ ( \lnot P \lor Q )$$ I am trying to solve this symbolic logic problem ^^ with the separation of cases inferences rule but I am having trouble.
0
votes
1answer
48 views

Solve this logical inference

I have the logic inference: Hypotheses: $A \implies (B \lor C)$ $A \lor (D \land B)$ Conclusion: $D \implies C$ I have these equivalence formations: Hypotheses: $A \lor (D \land B)$ $\lnot D ...
1
vote
1answer
61 views

Solve this tautology

Hypotheses: not $q$, $p$ or not $s$, $p \rightarrow$ ($d$ and $q$), $e \rightarrow s$ Conclusion: not $e$ I have thus far, but unsure how to proceed. I am looking forward to solve it using ...
1
vote
1answer
31 views

Problem with simplification in discrete math

I am doing my homework in discrete mathematics and I need your help.. I can' t find the way how to simplify this equation. I had to get Minimal Disjunctive Normal Form by just simplifying minimal ...
2
votes
1answer
38 views

Absorption Law with Negation

Would absorption law work for statements with neagations in them like $( \neg q \land \neg r) \lor r$?
0
votes
0answers
38 views

proving $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$

I looking for proof of $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$ in the foloowing logic (SJ logic in paper of Greg Restall , Subintuitionistic logic) $$⊢A→A$$ ...
-1
votes
2answers
43 views

To prove $A\rightarrow B, C\rightarrow D \vdash (A\vee C)\rightarrow (B\vee D)$ with natural deduction [closed]

How to prove this statement? $ A\rightarrow B, C\rightarrow D \vdash (A\vee C)\rightarrow (B\vee D)?$ in inference rule? tnx!
6
votes
5answers
240 views

Is a proposition about something which doesn't exist true or false?

Let S = {x | x is not an element of x } The set S doesn't exist. Then, would a proposition such as "The cardinality of S is 1," be true or false? Equivalently, I could have made a proposition, "the ...
2
votes
1answer
83 views

proving $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$

I'm looking for a way to prow $ (A \rightarrow B \vee C )\rightarrow((A\rightarrow B) \vee (A\rightarrow C))$ from the following axioms and rules $$\vdash A \rightarrow A$$ $$\vdash A \wedge B ...
0
votes
1answer
30 views

Showing logical equivalence of these two formulas

I have the following statement in propositional logic: (¬g v s1 v ¬s2) ^ (¬g v ¬s1 v s2) ^ (¬g v s1 v s2) (1) I want to show equivalence to this statement: ...
0
votes
0answers
36 views

Determine the truth values

Let P(x) : x^2 ≤ 4. Determine the truth values of the following propositions. Assume the domain for the variable is all positive integers: 1, 2, 3, 4, 5, and so on. ...
2
votes
1answer
32 views

translating phrases into propositional logic

translate the following into propositional logic: students attend the annual meetings where s: students A: attend annual meetings my first intuition is: s -> ...
0
votes
4answers
52 views

Can $(A \lor B) \land (\lnot A \land \lnot C)$ be more simplified?

Can $(A \lor B) \land (\lnot A \land \lnot C)$ be more simplified/expanded? With a kind of distributive property?
1
vote
2answers
40 views

Resolution on set of clauses

Given this set of clauses: $\neg \phi = (\neg T \lor \neg Y)\land (S \lor \neg X ) \land (\neg X \lor Z \lor \neg Y) \land(X \lor T) \land (Y \lor U) \land (Y \lor \neg V)\land \neg S \land V$ I ...
0
votes
4answers
56 views

proof for a problem in propositional logic

I cant find a proof for given problem: $$p \to ( q \to p) ≡ \lnot p \to ( p \to q ) $$ Please give proof to prove above statement.
0
votes
2answers
93 views

Finding a formal deduction from an empty set of premises

I can't seem to make sense of any of this. I'm given a set of axioms schemes, modus ponens as the inference rule and I'm supposed to find a formal deduction. The question (question 1) is here. It ...
2
votes
4answers
100 views

Question about logical implication $P\to Q$ [duplicate]

Having come across mathematical logic, a question suddenly came into my mind. We commonly know that the truth value of $P\to Q$ given as: $\begin{matrix} P&Q&P \Rightarrow Q \\ ...
2
votes
3answers
44 views

How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$

I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help. If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$. ...
2
votes
1answer
87 views

Problem with proving formally tautology using given rules

Using the rules below prove that the following assumeptions leads to the following conclusion by tautology. $A\vee B \vee C, A\to C, B\to C \Rightarrow C$ What I did: $A\vee B \vee ...
1
vote
1answer
43 views

Is the True clause considered the proof of resolution refutation

So, basically I have the sentence $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P \Rightarrow R))$$ and it was asked to prove it by resolution refutation. On the ...
1
vote
1answer
43 views

Conversion to CNF - eliminate implications

On the web I found a solution to an exercise on resoulution. Basically, it asks to use resolution refutation to prove $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P ...
1
vote
1answer
68 views

Propositional calculus logic question

In my assignment I have the following question: For every proposition $\theta$ let $E(\theta)$ be the set of basic propositions. Prove the following: For every two propositions, $\alpha$ and ...
5
votes
1answer
80 views

Compactness Theorem / Set made of formulas of infinite size

Could someone give me an example of an infinite countable set, where formulas contained in it are under the form of a conjunction or disjunction of infinite size, for which the compactness theorem ...
0
votes
1answer
28 views

How can I translate it into Logic sentence? [closed]

Let $p$ denote "it is snowing." So how can I translate the following into symbolic logic? "It is not snowing, but snowing." Please help me.
2
votes
1answer
73 views

Structural Induction, Propostitonal formulae problem

I am kind of overwhelmed by this question. Can anyone give me some hints about where to start? Propositional formulae PF are inductively defined over the Boolean constants B := {1, 0} (true and ...
1
vote
2answers
51 views

Prove the two logic expressions are equal

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$ It makes sense when I think about it, but how does one prove it? Also is there a relationship with the above and saying: $(a \implies ...
2
votes
2answers
113 views

Every element of the empty set has three toes true or false? [duplicate]

This is a bonus question that we have and I cannot figure it out. Any help would be great! Is the proposition Every element of the empty set has three toes true or false? Explain your answer
1
vote
0answers
28 views

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ [duplicate]

In a formal language, how does one show that $\neg \neg \bot \neq( \phi \wedge \psi) $ Or how do one go about showing that the former is not a proposition. I've just started reading Dalen's Logic and ...
0
votes
3answers
37 views

Question about negating implied propositions

I'm negating this proposition: "If you study you will not fail." I'm using proposition P: "You study" and proposition Q: "You will fail." The original statement can be written as "$P → ¬Q.$" My ...
1
vote
4answers
78 views

Basic logic question: Can $\neg p \implies p$ be true?

Can $\neg p \implies p$ be true? How about $p \implies \neg p$? I was told yes, but it doesn't make sense to me. Any help would be appreciated!
0
votes
1answer
37 views

Given $p \rightarrow q$ and p are true, show $q ∨ r$ is true using rules of inference

I have a question from computing mathematics which I am not really able to prove. Given that $p \rightarrow q$ and $p$ are true, show that $q \lor r$ is true using rules of inference. Any ...
1
vote
2answers
153 views

Proof of a theorem in Hilbert's system

I have been trying to prove that the propositional formula $ \big( \alpha \rightarrow \lnot \beta \big) \rightarrow \big((\alpha \rightarrow \beta) \rightarrow \lnot \alpha \big)$ is a theorem in ...
1
vote
4answers
98 views

Need Hints Prove “$((\neg \alpha \to \alpha) \to \alpha) $” Using Axiom 1,2,3 and MP and deduction theorem

$((\neg \alpha \to \alpha) \to \alpha) $ Hi, I am trying to prove this. Can someone gives me some hints to start the question... My friend told me I might need to use deduction theorem here, but I ...
1
vote
1answer
22 views

Proposotional logic derivation

Show that (φ ∧ ψ) ↔ ¬(φ → ¬ψ) is derivable. I have derived ¬(φ → ¬ψ) from (φ ∧ ψ) by assuming (φ → ¬ψ) and (φ ∧ ψ) and deducing a contradiction. By cancellation of the hypotheses I can then conclude ...
0
votes
1answer
25 views

Conjuctive normal form of $(p\wedge(q\implies r))\implies s$

I am asked to write this in CNF without using truth tables. This is what I worked out so far: $$(p\wedge(q\implies r))\implies s \\ \neg(p\wedge (q\implies r)) \vee s\\ (\neg p \vee \neg(\neg q \vee ...
1
vote
1answer
44 views

Prove that simple conditional statement is tautology

This should be pretty easy, but I don't know how to turn the conditional statement into a tauntology. The statement is: $$ (p \land q) \to p$$ I am able to turn it into: $$ (\lnot p \lor ...
0
votes
4answers
154 views

Solve this proof using tautologies (no truth tables)

I am having trouble solving this problem using tautologies (no truth tables). Hypotheses: $t \rightarrow s,\;\; d \rightarrow (u \vee t)$ Conclusion: $d \rightarrow ( u \vee s)$
1
vote
1answer
52 views

Show that the function is an isomorphism between two $L$-structure.

The function: $$f: \mathbb{R} \longrightarrow (-1, 1)$$ $$ x \rightarrow \frac{x}{1 + |x|}$$ is an isomorphism between $\langle\mathbb{R}, <, =\rangle $ and $\langle(-1, 1), <, =\rangle$ where ...
0
votes
1answer
53 views

Logical Consequences and Ordered Fields.

How do I show that these two: $1.$ $\forall x(0 < x \rightarrow (-x) < 0)$ $2.$ $\forall x \forall y \forall z((x<y \wedge z<0) \rightarrow (y *z) <(x*z))$ are logical consequences ...
1
vote
1answer
107 views

Conversion from English Language to Logic Symbols

I have a problem in an example of Discrete Mathematics which my teacher worked in his lecture. He gave an argument and proved it that his argument was not valid, but the validity of argument is not ...