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
398 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
1
vote
1answer
83 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. \ ...
1
vote
2answers
98 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 ...
2
votes
1answer
37 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 ...
5
votes
3answers
295 views

How to prove or statements

How do I prove statements of the following types: $A \text{ or } B \implies$ C $A \implies B \text{ or } C$ I don't know how to go about proving statements like this when they have "or". Can ...
3
votes
3answers
114 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 ...
0
votes
2answers
28 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 ...
3
votes
2answers
52 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 ...
3
votes
0answers
37 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 ...
6
votes
3answers
10k views

De-Morgan's theorem for 3 variables?

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'. I didn't find the answer for my question, therefore I'll ask here: ...
1
vote
3answers
289 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 ...
2
votes
2answers
98 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 ...
0
votes
1answer
30 views

Skolem Function and one Exam Challenge [closed]

we know if P implies Q (and show it by $P \Longrightarrow Q$ ), The Predicate Q is weaker than P. i want to check it which of the following is weaker than others? F1 is a Skolem function and F2 is a ...
2
votes
4answers
176 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 ...
0
votes
1answer
24 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.
0
votes
2answers
26 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
votes
1answer
53 views

Proving a Tautology Formally [closed]

I wish to prove: $(\neg p\leftrightarrow q)\leftrightarrow\neg(p\leftrightarrow q)$
0
votes
1answer
20 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.
1
vote
0answers
41 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
42 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 ...
0
votes
1answer
38 views

Solve by induction.

How would I show this equation is odd by using the induction hypothesis: $$ g(s) = 3(g(s-1))+(g(s-2))+1 $$ I was thinking that I would prove $g(s)$ is odd by $g(s+1) = 3(g(s)+g(s-1))+1$. How would I ...
0
votes
4answers
43 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
1answer
55 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
22 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
15 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
35 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$$ ...
0
votes
2answers
34 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
194 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
76 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 ...
1
vote
1answer
55 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 ...
0
votes
1answer
28 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
26 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
29 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 -> ...
1
vote
2answers
28 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 ...
2
votes
4answers
3k views

How do I prove the transitivity of a set of implications?

If I have a set of implications, how can I prove the transitivity? In other words: I know the transitivity law, but I need to show on paper for an assignment whether the argument is valid or not. $$ ...
-1
votes
0answers
33 views

Is $ \phi$ a propositional consequence of $\boldsymbol{\Gamma}$?

Let $\boldsymbol{\Gamma}$ be the set $$\{\forall P(x)\rightarrow \exists yQ(y) ,\exists yQ(y)\rightarrow P(x), \lnot P(x) \leftrightarrow(y=z)\}$$ $ \phi$ is $\forall P(x)\rightarrow \lnot(y=z)$. ...
2
votes
6answers
111 views

Showing that $\lnot Q \lor (\lnot Q \land R) = \lnot Q$ without a truth table

I've done a truth table after reducing it to this and it seems to be equal to $\neg Q$: $$\lnot Q \lor (\lnot Q \land R) = \lnot Q$$ But when I try to show it without a truth table (with just ...
0
votes
4answers
50 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.
-2
votes
2answers
81 views

Combinatorics homework problem [closed]

In how many ways can $23$ different books be given to $5$ students so that $2$ of the students will have $4$ books each and the other $3$ will have $5$ books each?
4
votes
5answers
75 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...
-1
votes
0answers
24 views

Equivalent sentences using logical connectives

Using only logical connectives implication ($\to $) and negation ($\lnot $), write a sentence equivalent to the sentence: $$ (p \land q ) \lor r $$ Using logical connectives disjunction ($\lor$) ...
0
votes
0answers
79 views

Let Γ = {p∧q,(¬p)∨q,p∨r}. Is it true that Γ ⊢ r?

I"m not sure how to solve this type of question. Here is the problem in more detail, and a similar problem: I know that given this set of formulas I'm supposed to show if its possible to deduce r ...
0
votes
2answers
77 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 ...
5
votes
2answers
2k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
-5
votes
1answer
71 views

Which if the following three propositions are logically equivalent? [closed]

Which if the following three propositions are logically equivalent? $(p \wedge q) \Rightarrow (p \wedge r)$ $p \wedge (q \Rightarrow (p \wedge r)) $ $(\lnot p) \vee (\neg q) \vee (r \wedge p)$ ...
2
votes
4answers
83 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 \\ ...
1
vote
1answer
35 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 ...
2
votes
3answers
41 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$. ...
0
votes
0answers
30 views

A mathematical statement is logically equivalent to a related statement

I have to finish the statement: A mathematical statement and its ____________ are logically equivalent. My guess is contrapositive but I do not think that's right. Any help will be appreciated. ...
2
votes
1answer
78 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 ...