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
5answers
134 views

Necessary but not sufficient in logic

I am working through sample questions and am having a bit of trouble understanding the solution. Write using logical connectives: p : Grizzly bears have been seen in the area. q : Hiking is safe on ...
1
vote
1answer
37 views

Are these two statements logically equivalent?

Are the statements $D \Rightarrow H \vee S$ and $(D \Rightarrow H) \vee (D \Rightarrow S)$ logically equivalent?
3
votes
1answer
34 views

prove that $\Sigma \vdash \phi_1$ and $\Sigma \vdash \phi_2$ leads to $\Sigma \vdash \phi_1 \wedge \phi_2$.

I try to prove that if $\Sigma \vdash \phi_1$ and $\Sigma \vdash \phi_2$ then $\Sigma \vdash \phi_1 \wedge \phi_2$. Notice that, the ONLY rule of inference of the system is modes ponens and the set ...
0
votes
2answers
187 views

Discrete Math - Determine if the argument is valid

Can you guys please check my work and syntax. Question: Determine if the argument is valid. p $\rightarrow $ q $\underline{\urcorner{q}}$ $\therefore \urcorner$p Answer: T $\rightarrow $ T ...
2
votes
1answer
67 views

Partial truth table and proving or disproving tautology

Let $p,q$ be elementry statements and $\alpha,\beta,\gamma$ be statements. (sorry if this is the wrong translation). Prove/disprove: is $p,q\Rightarrow \gamma$ tautology? is ...
2
votes
2answers
47 views

Associativity and De Morgan's for more than 2 literals

Do logical operators have meaning when used with more than 2 literals "associatively", e.g.: $(A \land B \land C)$? I.e., are statements such as $(A \land B \land C)$ meaningful, as opposed to $((A ...
0
votes
1answer
403 views

Proving each conditional statement is a tautology

I'm having trouble trying to show that each of the conditional statement below is a tautology without using a truth table. I'm assuming you would have to use logical equivalence to figure this out. I ...
1
vote
1answer
58 views

Logically determining the validity of a statement

I'm having some trouble determining if the following statement may be considered valid. if the apples are on sale, I will buy the apples. the apples are not on sale. ∴ I will not buy the apples. ...
0
votes
2answers
35 views

Logical disjunction truth table

The truth table for a logical disjunction shows that there is only one situation where the result can be false, being when both statements are false. As long as one statement is true, the result is ...
2
votes
2answers
68 views

Notation or verbiage for the opposite of 'iff'? [duplicate]

Given the statement $X \implies Y$ and $Y \implies X$, we have the common notation $X \iff Y$. Ok so is there an opposite of this concept? Suppose I have $X$ doesn't imply $Y$, nor does $Y$ imply ...
1
vote
1answer
131 views

Need help understanding discrete mathematics logic

I am having a heck of a time understanding Discrete Mathematics. I have tried this myself and put my answer below. If anyone could help me if my answer is incorrect could you please explain to me what ...
2
votes
2answers
108 views

Are the following logically equivalent? $\;p \rightarrow (q \rightarrow r) \text{ and }\ (p \rightarrow q) \rightarrow r$

Determine whether the following pair of statements are logically equivalent or not... $$p \rightarrow (q \rightarrow r) \;\;\text{ and }\;\; (p \rightarrow q) \rightarrow r$$ I am new to logic ...
-1
votes
1answer
17 views

How to identify invalid proposition

In propositional logic, how do i identify if a [compound/non-compound] proposition is valid or not? do the parenthesis matter, even if they start and do not end etc...? for example: ...
1
vote
1answer
63 views

Complicated FOL Formula {∃a,c(a≠c) ∧ ∀a,c[(a≠c)⇒(h(a,c)⟺ ¬h(c,a))] ∧ ∀a,c[h(a,c) ⇒ ∃b(h(a,b)∧h(b,c)∧b≠c)]} ⇒ ¬{∃a∀b[b≠a⇒ h(a,b)]}

In preparing for an exam, I'm working through old exam questions and am now trying to figure out if the following first-order formula is valid and if not, then give a model that does not satisfy the ...
0
votes
2answers
19 views

simplification of a propositional statement

Write the formula which is equivalent to the formula $$\neg (p\leftrightarrow(q\to(r \lor p)))$$ and contains the connectives AND ( $\land$ ) and NEGATION ( $\neg$ ) only.
1
vote
1answer
37 views

If $\Sigma$ satisfies $\alpha$ and also not-$\alpha$ then $\Sigma$ is not satisfiable?

Why is it true that if $\Sigma$ satisfies $\alpha$ and also not-$\alpha$ then $\Sigma$ is not satisfiable? Is it true at all? it doesn't make any sense to me and I would like to know more about that ...
0
votes
1answer
71 views

How to prove this using natural deduction

⊢ P ∨ ¬P I found this question on the net. I know the solution but i find it complicated. How should i approach to this sort of question? Or can you provide me another solution ?
3
votes
0answers
63 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
5
votes
1answer
141 views

How to formally prove the negation of a statement “A if and only if B”?

Motivated by this question, I'm trying to establish a logical proof to the fact that the following statement is false: $2x+1$ is prime if and only if $x$ is prime. There are several ways to ...
5
votes
1answer
59 views

Rewriting $X\leftrightarrow Y$ using only $\neg$ and $\lor$

Note: The book I'm using doesn't have any solutions/answers so I will be posting some of the questions I'm unsure about in the hope that someone will check it for me. Question: Re-write ...
2
votes
1answer
46 views

Statement calculus

Turn the statement 'either $X$ or $Y$' into an iterated composition. I'm not sure if my answer is correct, can someone please check for me? : $$\text{either }X\text{ or }Y \equiv (X\vee Y)\wedge ...
3
votes
2answers
67 views

Establishing the validity of an argument.

I've been trying to determine the validity of a particular argument for some time now and I've had no luck in figuring it out. The argument in question goes as follows: \begin{align} & p \wedge q ...
1
vote
2answers
40 views

proof for propositional logic

I am unable to prove the following proposition logic. $(p \lor \neg r) \land (r \lor \neg p) \leftrightarrow (p \leftrightarrow q) \land (q \leftrightarrow r)$ My solution is given in the image. ...
2
votes
1answer
52 views

Consistency vs Inconsistency in a set of sentences: which is more common

I'm curious whether there is any research in the "probability" that a set of sentences in a first-order logic is consistent. Obviously, there are an infinite number of inconsistent sets and an ...
0
votes
2answers
34 views

Propositional formula, consisting of $p, q, r$ is true iff only one of them is true

I have some difficulties in building a formula $\phi(p, q, r)$, which is true iff only one of the variables is true. I suppose that it's reasonably to start trying, using the truth table, but ...
4
votes
0answers
63 views

(Co)homology of propositional logic

Sorry if this is a rather vague question, but it seemed like something that might be interesting. Let $P$ be a family of propositions, and let $\mathcal L(P)$ be the set of all compound propositions ...
1
vote
2answers
148 views

Prove $( \lnot C \implies \lnot B) \implies (B \implies C)$ without the Deduction Theorem

The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove $(\lnot C\implies\lnot B)\implies(B\implies C)$ by using the three axioms $(A1,A2,A3)$ without using ...
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
117 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
224 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
98 views

Proving a Tautology Formally [closed]

I wish to prove: $(\neg p\leftrightarrow q)\leftrightarrow\neg(p\leftrightarrow q)$
0
votes
2answers
32 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
44 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
65 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
49 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
39 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
39 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
49 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
252 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: ...
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
49 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 ...