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)

0
votes
2answers
84 views

Why $ M\models \forall x ( \alpha \to \beta)$ Is False? [closed]

if M be a model and $\alpha$ and $ \beta$ be two formula the following is False: $ M \models \forall x ( \alpha \to \beta)$ if and only if $ M \models \forall x \alpha$ has conclusion $ M \models ...
0
votes
1answer
54 views

Proving these are logically equivalent?

How to prove that these are logically equivalent using laws? a. $p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)$ I used the Conditional law and DeMorgan's Law and eventually arrived at $-(p ∨ q) ∧ -(p ∨ q)$ but ...
0
votes
0answers
41 views

Proof by contradiction that $P \rightarrow Q$ is true

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. So let's say the statement can be expressed by $P \rightarrow Q$. To prove that this statement is true, we look at the assumption ...
0
votes
1answer
28 views

Logical Equivalence of Wffs in Sentence, Predicate Logic using Tables, Interpretations Resp.

just curious if there is a formal name for the results that: a) Two wffs in Sentence Logic are equivalent iff their truth tables are equal , as binary functions of {T,F} b) Two wffs A,B in ...
3
votes
3answers
90 views

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. Is this valid?

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. I would say that this is false since the weather isn't directly influencing John's health. Am I right or wrong? Should I use ...
2
votes
1answer
76 views

What is the _simplest_ way to solve problems of this kind?

Two doors with talking doorknockers - one always tells the truth and one always lies. One door leads to death other to escape. Only one question may be asked to either of the door knockers. What would ...
2
votes
3answers
75 views

What is the negation of the statement “Every odd nmber is divisible by 2”.

Intuitively,I think it is "no odd number is divisible by 2" or it could be "every odd number is not divisible by 2". Is this a trivial question or is there more to it? What is the correct answer? BTW ...
4
votes
9answers
203 views

Why is the negation of $A \Rightarrow B$ not $A \Rightarrow \lnot B$?

The book I am reading says that the negation of "$A$ implies $B$" is "$A$ does not necessarily imply $B$" and not "$A$ implies not $B$". I understand the distinction between the two cases but why is ...
0
votes
0answers
34 views

Non Satisfiability of disjuction

Problem: If S1,S2 are (possibly infinite) sets of propositional formulas where their union: S1VS2 is not satisfiable, prove that there exists an ψ such that S1|=ψ and S2|=¬ψ. Can we say that if ...
1
vote
1answer
64 views

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable.

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. Okay can prove this by contradiction. So we say that a tableau $\tau$ is $\textit{satisfiable}$ iff there exists an ...
1
vote
1answer
84 views

direct hint to showing a formula is valid?

we know A formula is logically valid (or simply valid) if it is true in every interpretation. These formulas play a role similar to tautologies in propositional logic. which one could direct me to ...
4
votes
1answer
56 views

Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$

Question: Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$ Answer: (1) Let, ...
0
votes
1answer
43 views

how we can prove that argument $P_1,P_2,…,P_n $?

I ran into a one claims on LOGIC. how can add more direction or hint to me? if we have an argument $P_1,P_2,...,P_n $ such that $ n>3$ ($p_i$ is premise) why $P_1,P_2,....,P_n,P_1$ is ...
1
vote
0answers
37 views

How we can prove that the logical result of a set is effectively enumerable? [duplicate]

How we can prove that the logical result of $\{(p_i \vee $~ $p_{i+1}$$) $$: i \in \mathbb{N} \}$ is effectively enumerable ? Update: as one user requests, I add my method. I use truth table for ...
0
votes
1answer
43 views

Proving tautology without using truth tables

I have a statement (P∧Q∧(R∧P⇒~Q))⇒~R that I need to prove tautology without using truth tables. I understand I'll be using inference rules. Here's what I've tried ...
1
vote
2answers
45 views

Maximal consistency proof for set of propositional logic with specific restriction?

I ran into struggle when I comes to one sentence on logic. Why the set of all propositional that under any valuation has value 1 is not maximal consistent ? ...
0
votes
0answers
48 views

Interpretation and truth table is enough to showing validity or a better way?

I'm so glad that find this useful site. anyway, I ran into some challenging ways to find a formula is valid. Here is two example in my note that called valid. I ran into such a problem with making ...
2
votes
1answer
70 views

RAA elimination and inference a theory ?!

Can somebody explain the why if we eliminate RAA rule in natural deduction system on propositional logic, why ~$(p \wedge $~$p)$ is not inference from the ...
0
votes
2answers
50 views

Valid Formula in First Order Logic

I am a little confused about the validity of first order logic formulas. How we can using formal notation to prove the following is VALID? $ \exists x \exists ...
0
votes
3answers
89 views

'If…then…' and '…if…' and '…only if…' and 'If… only then…' statements?

Suppose you have two statements A and B and "If A then B". I am trying to think of what this implies and alternative ways of writing this. I think "If A then B" = A$\rightarrow$B = "A is ...
0
votes
0answers
34 views

Formalize “Statement $A$ is the correct explanation of statement $B$”

If I have two statements. Let say Statement $A$ and Statement $B$. What will be the necessary condition or how to write the following conditions mathematically? Statement $A$ is the correct ...
1
vote
1answer
41 views

Why if the antecedent P is false, and the consequence Q true, then the implication P $\Rightarrow$ Q is true? [duplicate]

I know that that's the definition but I wonder why logicians choose that thefinition to be true. It sounds strange to me and I cant make sense of it if someone tell me 'if the sky is red, then I'm ...
0
votes
1answer
57 views

Let $\tau$ and $\rho$ be tableaus such that $\tau \leadsto \rho$. Prove that $\tau$ is satisfiable if and only if $\rho$ is satisfiable.

I have this definition: Let $\nu$ be any propositional interpretation. Let $b$ be any branch of a tableau. Say that $\nu$ is faithful to b if and only if for every formula, $A$, on the branch, ...
-3
votes
1answer
34 views

Can boolean logic compute any sort of mathematical operation?

Computers fundamentally do logical operations on the input and memory they have (as far as I know). Computers are used by mathematicians to do all sorts of mathsy operations (as far as I know). Does ...
2
votes
1answer
87 views

What is the difference between Boolean logic and propositional logic?

As far as I can see, they only employ different symbols but they operate in the same way. Am I missing something? I wanted to write "Boolean logic" in the tag box but a message came up saying that if ...
1
vote
1answer
43 views

Showing $(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$ by distributive law(s)

I want to show that $$(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$$ by one of the two Distributivity Laws: $$P\wedge(Q\vee R)\equiv(P\wedge Q)\vee(P\wedge R)$$ $$P\vee(Q\wedge R)\equiv(P\vee ...
0
votes
1answer
40 views

Why is that: $P \Rightarrow T$, truth value(P) = ?, but $(P\Rightarrow F) \Rightarrow$ Truth value (P) = F

Why is that: If: P :proposition. T: true statement F: false statement $$P \Rightarrow T $$ In this statement, we can not have for sure the Truth value of P (if P is T or F) , but, in this ...
0
votes
2answers
172 views

Completness and Set of Result of One Set ?!?

Dear Everyone on this Wonderful Sites: I'm so glad to participate on this site and ask the first question that mentioned on the Contest some days ago. I ran into a question that wrote this set: ...
0
votes
2answers
56 views

Do all logic problems have one solution? [closed]

Analyze the logical forms of the following statements: x and y are natural numbers, and exactly one of them is prime. Below are the two answers that I got. The first one is the one the author ...
2
votes
1answer
33 views

How does distribution work in logic?

Hi guys A question regarding propositional logic. ¬(¬P∧Q)∨(P∧¬R) = (P∨¬Q)∨(P∧¬R) ...DeMorgan's, Double Negation law = ((P∨¬Q)∨P)∧((P∨¬Q)∨¬R) ...Distribution law = (P∨¬Q)∧((P∨¬Q)∨¬R) ...
1
vote
1answer
24 views

Can I use two inferred clauses to get the empty set?

In resolution can I use two inferred clauses to reach the empty set? Consider this set of clauses: $\{ p \lor q,\neg p \lor r, \neg p \lor \neg r, p \lor \neg q\}$ \begin{align*} \quad p \lor ...
2
votes
2answers
55 views

How do I show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are NOT logically equivalent?

Show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are not logically equivalent. Can someone give a hint?
1
vote
1answer
52 views

$P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations.

Suppose that the domain of the propositional function $P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations. a) ...
1
vote
2answers
104 views

Truth table of proof by contradiction

The following is the truth table for an implication: $(T\Rightarrow T) = T$ $(T\Rightarrow F) = F$ $(F\Rightarrow T) = T$ $(F\Rightarrow F) = T$ Now, in an implication involved in a proof by ...
0
votes
2answers
37 views

The propositional logic expression for ∃x∀yP(x,y)

Where u.d. of x is {1,2,3} and y is {a,b} The given answer is ((1,a)Λ(1,b)) V ((2,a)Λ(2,b)) V ((3,a)Λ(3,b)) But I get the expression ((1,a)V(2,a)V(3,a)) Λ ((1,b)V(2,b)V(3,b)) Why is my one wrong ...
2
votes
3answers
39 views

Proving logical equivalences

The question is to prove $\neg (p \wedge q) \to (p \vee r)$ equivalent to $p \vee r$ So far, I got $¬[¬(p \wedge q)] \vee (p \vee r)$ - implication $(p \wedge q) \vee (p \vee r)$ - ...
0
votes
1answer
21 views

Simpliest Propositional Equivalences proof question

I'm solving some propositional equivalences questions and I just want to make sure that following two logics. If, $p \land q = q \land p$ $p \vee q = q \vee p$ in any case, are correct because ...
1
vote
1answer
47 views

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators.

Earlier this day I ask about the assignmet: Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators. I was given the hint that I could use De Morgan law to show ...
0
votes
5answers
112 views

Logical equivalent of $p\to(q\to p)$

Is Logical equivalent of $p\to(q\to p)$, $p\to(p\wedge q)$ or $p\to(p\vee q)$? I have a truth table: $$\begin{array}{c|c|c|c} p&q&p\wedge q&p\vee q&q\to p&p\to(q\to ...
0
votes
1answer
29 views

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators [duplicate]

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators Can someone give a hint?
1
vote
1answer
46 views

How can I show logically equivalence without a truth table

Show that $(p \rightarrow q) \wedge (p \rightarrow r)$ and $p \rightarrow (q \wedge r)$ are logically equivalent. I tried to do this making a truth table but I think my teacher wants me to solve it ...
0
votes
1answer
28 views

Logic question in propositional calculus

How do we prove the following formula for all natural numbers $n$ in propositional calculus $[(q_{1}\vee q_{2}...q_{n})\wedge((q_{1}\Longrightarrow r)\wedge(q_{2}\Longrightarrow ...
1
vote
0answers
72 views

Proving $\vdash (p\to q)\lor (q\to r)$ using natural deduction

I'm trying to prove the following: $\vdash (p\to q)\lor(q\to r)$ using only intuitionistically valid rules. I've tried a few different ways, and I think my problem is that I'm not sure what ...
1
vote
2answers
56 views

Value V on some formula in Logic

I want to calculate, how many value $v$ on {$p,q,r$} has, such that sentence $(p \to (q\wedge r)) \to r$ gets value $0$? I solve it via truth table, any other methods for solving such questions? or ...
1
vote
2answers
25 views

How to express sample space

I have been given No answers though please!
0
votes
2answers
73 views

Question about propositional logic

I was just learning the truth table of the propositional logic . I understand the truth table for the conjunction and disjunction because they make sense in the real life. The conjunction A∧B means "A ...
0
votes
0answers
8 views

how many symantec equations is there in propositional calculus with n boolean variables?

how many symantec equations is there in propositional calculus with n boolean variables? The answers are: 1) 3^n 2) n 3) 2^(2n) 4) 2^n I think the answer is 2^n. Do you think its correct? ...
0
votes
1answer
57 views

Admissible rule in classic logic [closed]

The classical propositional logic admits the concept of admissible rule, and would like some examples of propositional calculus with the 'admissible rule', on wikipedia I don't quite understand...
1
vote
0answers
33 views

Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
1
vote
0answers
31 views

Can the OR function be linearly separated?

I have two questions regarding linear functions and propositional calculus: 1) How do you decide if, for example, the OR function can be linearly separated? The answer is Yes, however I don't know ...