CS360 - Artificial Intelligence Fundamentals 笔记

小毛龙

开个坑整理笔记.jpg

小毛龙

Lecture 01. Introduction

全是废话，不写了

小毛龙

Lecture 02. Intelligent Agents

Agents and Environments

Agents

An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.

Precept

Agent’s perceptual inputs at any given instant.

Precept Sequence

The complete history of everything the agent has ever perceived.

Agent’s choice of action at any given time can depend on the entire precept sequence observed to date.
6

Agent Function

The agent function f maps from percept histories to actions.

f: P^* \rightarrow A

Rationality

Performance Measure (Utility Function)

An objective criterion for success of an agent's behavior.

Rational Agent

For each possible precept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the precept sequence and the agent’s built-in knowledge.

Rationality is distinct from omniscience (all-knowing with infinite knowledge).

Precepts may not supply all the relevant information.
Consequences of actions may be unpredictable.

An agent is autonomous if its behavior is determined by its own experience (with ability to learn and adapt to environment).

PEAS

Term PEAS is used in problem specification, standing for:

Performance Measure
Environment
Actuators
Sensors

Environment Types

There are multiple dimension regards the classification of environments, some of the dimensions are:

Fully Observable (vs. Partially Observable)
The agent's sensors give it access to the complete state of the environment at each point in time.
Deterministic (vs. Stochastic)
The next state of the environment is completely determined by the current state and the agent’s action.
- Strategic: the environment is deterministic except for the actions of other agents.
Episodic (vs. Sequential)
The agent's experience is divided into atomic “episodes,” and the choice of action in each episode depends only on the episode itself.
Static (vs. Dynamic)
The environment is unchanged while an agent is deliberating.
- Semi-dynamic
  the environment does not change with the passage of time, but the agent's performance score does (like in most turn-based games).
Discrete (vs. continuous)
The environment provides a fixed number of distinct precepts, actions, and environment states. Time can also evolve in a discrete or continuous fashion.
Single-agent (vs. Multi-agent)
An agent operating by itself in an environment
Known (vs. Unknown)
The agent knows the rules of the environment

Agent Types

Table-lookup Agent

A trivial agent program: keeps track of the precept sequence and then uses it to index into a table of actions to decide what to do. The designers must construct the table that contains the appropriate action for every possible precept sequence.

Drawbacks:

Huge table, take a long time to build
No autonomy
Even with learning, need a long time to learn the table entries

Simple Reflex Agents

Model-based Reflex Agent

Goal-based Agent

Utility-based Agent

Learning Agent

小毛龙

Lecture 03. Problem Solving and Search

Search Problem

A search problem consists of a search space and a goal condition.

The search space is the set of object among which we search for the solution.

The goal condition is the characteristics of the object we are trying to find in the search space.

Searching

Searching is the process of exploration of the search space.

The efficiency of the search depends on the search space and its size, the method used to traverse the search space and the condition to test the satisfaction of the search goal. This efficiency could be optimized by using smarter tactics when choosing the search space, the exploration method, and the design of the goal test.

Graph Representation of a Search Problem

Search problems can often be represented using graphs, a typical example of such problem is path finding.

A more complex problem may assign costs to each edge of the graph, and ask to find the path with the maximum/minimum cost.

Depending on the nature of the problem, the graph search often falls under two categories:

Path Search, that we want to find a path between vertex S and T with some constraint.
Configuration Search, that we want to find a vertex S that satisfies a given constraint.

A graph search problem can be formulated as:

Initial State: The state where the search starts
Operators: The transformation from one state to another
Goal Condition: The definition of the target state
Search Space: The set of objects we search for the goal. This can be defined with Initial State + Operators.
(Problem Type): Is the answer a path or a specific state?
(Possible Solution Cost): What is the cost from the initial state to goal might be?

Search Tree

A search tree is a structure that representing the exploration trace. The tree is built dynamically during the searching process with its branches corresponding to explored paths and leaves to the fringe of exploration. A branch in the search tree corresponds a path in the search space.

Note
The search tree is not simply a transformation of the state space. Depending on the implementation of search algorithm, a node may reappear multiple times on the search tree while there is only one of itself in the search space.

Implementation of Searching

Queuing Function

The explore strategy can often be viewed as an queuing function that determine which node will be selected next.

Search Tree Node

A search tree node is a data structure that maintains information such as the state description, the cost of this state, its depth in the search tree and the cumulative path cost to this node.

Search Algorithms (Uninformed)

Search Algorithms, or Search Methods, have following properties:

Completeness: Does the algorithm find the solution, or all existing solutions?
Optimal: Is the solution returned optimal?
Complexity: How many time and memory is required to perform the algorithm?

Generic Search Algorithm

def generic_search(problem, strategy):
    search_tree = SearchTree(problem.initial_state)
    while True:
        if strategy.candidate_states == 0: return SolutionNotFoundException
        
        next_node = strategy.get_next_expand_node()
        if problem.goal == next_node: 
             solution = strategy.pack_solution(next_node)
             return solution
        else: strategy.expand_node(next_node)

Breadth First Search

BFS always expand the shallowest node.
When expanding a node, its successors are enqueued to the end of the queue in FIFO manner.

Completeness: True
Optimal: True (for the sortest path problems)
Complexity:
For a search tree with branching factor of b and depth of d:
- Time Complexity: O(b^d) - EXPONENTIAL
- Space Complexity: O(b^d) - EXPONENTIAL

Depth First Search

DFS always expands the deepest node, and backtracks when the current node could not be expanded.

Completeness: False (possible for infinite loops)
- Can be avoided by setting a depth limit, or introduce a cycle prevention mechanism.
Optimal: False (for the sortest path problems)
Complexity:
For a search tree with branching factor of b and max-depth of d:
- Time Complexity: O(b^d) - EXPONENTIAL
- Space Complexity: O(b\times d) - LINEAR

Iterative Deepening

The idea of this algorithm is try searching using DFS with a depth limit, if the solution is not reach, then increase the depth limit by a certain amount. Repeat until the solution is reached.

Completeness: True
Optimal: True (for the sortest path problems)
Complexity:
For a search tree with branching factor of b and max-depth of d:
- Time Complexity: O(b^d) - EXPONENTIAL
- Space Complexity: O(b\times d) - LINEAR

Bi-directional Search

This algorithm is used in some search problems we need to find the path from the initial state to a unique goal state.

The idea is to initiate search both from initial and goal state, and use inverse operators for goal-initiated search.

The strength of this method is if a state is found both in initial and goal initiated state, the two state can be "linked" even they are on different search tree, and a path can be constructed, thus cuts down search tree by half.

This search uses a path cost function assigned for node n, called g(n). The search strategy is to expand a leaf node with minimum g(n) first.

Uniform Cost Search

Always expand the node with least cumulative path cost.

Completeness: True
Optimal: True (for the sortest path problems)
Complexity:
For a search tree with branching factor of b and max-depth of d, assuming the solution costs g and the minimum arc cost is \varepsilon:
- Time Complexity: O(b^{g/\varepsilon}) - EXPONENTIAL
- Space Complexity: O(b^{g/\varepsilon}) - EXPONENTIAL

Search Algorithms (Informed)

An informed search algorithm, or a heuristic search algorithm, it is built upon the evaluation-function driven search, which is a search strategy that utilizes a node evaluation function f(n) to define the desirability of a node to be expanded next. Generally, this type of search algorithms expand the node with the best evaluation function value and is implemented with a priority queue.

Heuristic search algorithm further utilizes a heuristic function h(n) to evaluate the "potential" for a node to reach the desired state, and the order of node expansion is concerned with the combination of g(n) and h(n).

Admissible Heuristics
If a heuristic function h(n) never overstimates the distance of a node to the goal, noted h*(n), then the heuristic is called admissible.
It is possible to have mulitple admissible huristics of the same problem.

Heuristic function h_2 dominates h_1 if \forall n, h_2(n) \ge h_1(n).
Two admissible heuristic function can be combined to create a new admissible heuristic: h_3(n) = \max(h_1(n), h_2(n))

Heuristic can be created using a version of problem that have fewer constraints on the actions, called a relaxed problem.

Best-first Search

This search algorithm always expand the node "seems" to be the closest to the goal first.

When f(n) = h(n), this algorithm is the same as Greedy Search.
- Completeness: False (Possible for infinite loop with repeat elimination)
- Optimal: False (f(n) does not respect g(n))
- Complexity:
  For a search tree with branching factor of b and max-depth of d, assuming the solution costs g and the minimum arc cost is \varepsilon:
  - Time Complexity: O(b^m) - EXPONENTIAL (worst, avg is better)
  - Space Complexity: O(b^m) - EXPONENTIAL (worst, avg is better)
When f(n) = g(n) + h(n), this algorithm is A* algorithm, where g(n) is the path cost function from initial node to node n. (If combined with iterative deepening, this creates a special version of A* called IDA*.)
- Completeness: True
- Optimal: False (for any given heuristic function)
- Complexity:
  For a search tree with branching factor of b and max-depth of d, assuming the solution costs g and the minimum arc cost is \varepsilon:
  - Time Complexity: Number of nodes which f(n) is less than cost of the optimal path.
  - Space Complexity: Same as time complexity.

IDA*

IDA* performs a limited-cost DFS for a evaluation function limit, and progressively increase the evaluation function limit until a solution is found.

One problem of this algorithm is the determine of increment of the limit, which have two tactics:

Peak over the previous step boundary to guarantee that new node is expanded in the next cycle
Increase by fixed amount

Completeness: True
Optimal: True (for the sortest path problems)
Complexity:
For a search tree with branching factor of b and max-depth of d:
- Time Complexity: O(b^d) - EXPONENTIAL
- Space Complexity: O(b\times d) - LINEAR

小毛龙

Lecture 04. Beyond Classical Search

In many problems, the path to the goal is irrelevant, the goal state is what we want.

For this kind of problem, the local search algorithms can be used. This algorithm maintains a current state and try to improve upon it.

Hill-climbing Search

Hill-climbing search is a greedy approach to local search where the algorithm will always choose the local maxima as the next state.

def hill_climbing_search(problem):
    current = problem.initial_state
    while True:
        neighbor = current.successors.highest()
        if neighbor.value() <= current.value(): return current
        current = neighbor

The problem of this algorithm is that it may get stuck in local maximum, which might not be globally optimal.

Simulated Annealing Search

The idea of this algorithm is to allow some bad moves but gradually decrease their frequency.

def simulated_annealing_search(problem):
    current = problem.initial_state
    elapsed_time = 0

    while True:
        elapsed_time += 1
        T = update_temperature(elapsed_time, T)    # T will decrease over time
        if T == 0: return current

        next = current.successors.random()
        dE = next.value() - current.value()

        if dE > 0: current = next
        else:
          if random_check(prob = e**(- dE/T)):
               # if e^(- dE/T) > random number in (0, 1), the check is passed
              current = next

If T decrease slowly enough, then this algorithm will find the global optimum with probability approaching 1. This algorithm assumes that annealing will continue until T reaches 0.

The most common way of implementing an SA algorithm is first implement a hill climbing with an accept function and modify it for SA by introducing a cooling schedule. (In the code above, it is update_temperature())

Cooling Schedule

Starting Temperature

Lower limit: the starting temperature must be hot enough so that the moves to worse neighborhood state is allowed, otherwise the algorithm will degrade to hill climbing.
Upper limit: the starting temperature must not be so hot or the algorithm will do random search in a initial period of time.

Some trial-and-error may required for an optimal starting temperature.

Final Temperature

Usually implemented as 0, however this can make the algorithm take longer to complete, especially when a geometric cooling schedule is being used. In practice the threshold is implemented higher.

Temperature Decrement

Linear: T = T - c
Geometric: T = T*c
- Experience shown that the optimal range for c is [0.8, 0.99]

Iterations at Each Temperature

We can dynamically change the number of iterations at each temperature as the algorithm progresses.

At higher temperatures, the iteration can be less, but in lower temperature it is important to iterate multiple times ti ensure the local optimum is fully explored.

Acceptance Probability

The exponential calculation is computationally expensive, so an alternative P(\delta) = 1 - \delta/t can be used to approximate the exponential.

Local Beam Search

This algorithm is like a parallel version of hill-climbing search.

It keeps track of k states simultaneously.
Initially the algorithm starts with k randomly generated states.
In each iteration, all the successors of those k states are generated.
If goal is present in generated states, the algorithm stops.
Otherwise it selects k best successors from all states expanded and repeat.

Genetic Algorithms

This algorithm is designed to mimic the process of biological evolution. In this algorithm:

A state is represented as a string over a finite alphabet, often a binary string.
A successor state is generated by combining two parent states.
An evaluation function, or fitness function is present. Higher values means the state is better.
The algorithm starts with k randomly generated states, called population .
The next generation is generated by selection, crossover and mutation.

小毛龙

Lecture 05. Adversarial Search and Game Playing

Games vs. Search Problems

The opponent's actions may be unpredictable.
The game usually requires a result in reasonable time, so efficiency is critical.
The game could be deterministic or chances may apply, and the information the algorithm can observe could be complete or imperfect.

Alternating Two-Player Zero-Sum Games

Players takes turns
Each game outcome, or terminal state has a utility for each player:
- +1 - Win
- 0 - Tie
- -1 - Lose
The sum of both players' utilities is a constant.

The game tree discussed is a two-player, turn-taking, deterministic, fully observable, zero-sum, time-constrained game. Assuming a viewpoint from player MAX.

Minimax Algorithm

Using the current state as the initial state, build the game tree uniformly to the maximal depth m (called horizon) feasible within the time limit. The larger value means the state is more favorable to MAX.
Evaluate the states of the leaf nodes.
- An evaluation is required in this step. The function is a heuristic that estimates the feasibility of a state for MAX.
- The construction of an evaluation function is usually a weighted sum of features include number of piece of each type, number of possible moves, etc.
Back up the results from the leaves to the root and pick the best action assuming the worst from MIN.
- For MIN controlled nodes, the heuristic of the node is the minimum value of all its successors
- For MAX controlled nodes, the heuristic of the node is the maximum value of all its successors
Select the move towards a MIN controlled node that has the largest backed-up value.

def minimax(state): action
    v = max_value(state)
    return state.successors(value = v).action

def max_value(state): int
    if state.is_terminal(): return state.utility
    else:
        v = -INFINITY
        for s in state.successors():
            v = max(v, min_value(s))
    return v

def min_value(state): int
    if state.is_terminal(): return state.utility
    else:
        v = INFINITY
        for s in state.successors():
            v = min(v, max_value(s))
    return v

Completeness: True (for finite tree)
Optimal: True (against an optimal opponent)
Complexity:
For a search tree with branching factor of b and horizon m:
- Time Complexity: O(b^m) - EXPONENTIAL
- Space Complexity: O(b\times m) - LINEAR (DFS)

Alpha-Beta Pruning

In this algorithm, a pruning mechanism is used to not explore unpromising subtrees.
Each MAX controlled node have a \alpha value and MIN controlled node have a \beta value.

The \alpha value of a MAX controlled node is a lower bound on the final backed-up value
The \beta value of a MIN controlled node is a upper bound on the final backed-up value

When searching:

Update the \alpha/\beta value of the node if any search below the node has completed or aborted
Conduct search in following rules:
- For MAX controlled nodes, if its \alpha \ge \beta of any MIN controlled ancestors, search below this node is aborted
- For MIN controlled nodes, if its \beta \le \alpha of any MAX controlled ancestors, search below this node is aborted.

def alpha_beta_search(state): action
    v = max_value(state, -INFINITY, INFINITY)
    return state.successors(value = v).action

def max_value(state, alpha, beta): int
    if state.is_terminal(): return state.utility
    else:
        v = -INFINITY
        for s in state.successors():
            v = max(v, min_value(s, alpha, beta))
            if v >= beta: return v
            alpha = max(alpha, v)
    return v

def min_value(state, alpha, beta): int
    if state.is_terminal(): return state.utility
    else:
        v = INFINITY
        for s in state.successors():
            v = min(v, max_value(s, alpha, beta))
            if v <= alpha: return v
            beta = min(beta, v)
    return v

In practice the terminal test is often replaced by a cutoff test, that limits the depth of search to satisfy a time constraint. However this may leads to the incorrest estimation due to incomplete infoemation. This problem may be solved by not cut off search at positions that is too unstable, or a strong move should be tried when normal depth limit is reached.

Other techniques including building cache tables, or store several predefined move tables to accelerate the search process, or the horizon can be adjusted dynamically.

Other Types of Games

小毛龙

Lecture 06. Constraint Satisfaction

Where we postpone making difficult decisions until they become easy to make.

Constraint Satisfaction Problem

A CSP consist of:

A set of variables {X_1, X_2, \dots, X_n}.
Each variable X_i is in a domain D_i which is usually finite
- If domain is infinite, this problem is called an infinite CSP, which we will not consider in this course.
A set of constraints {C_1, C_2, \dots, C_p}
- Each constraint relates a subset of variables by specifying the valid combinations of their values.
- Type of Constraints
  - Unary Constraints: Involves a single variable
  - Binary Constraints: Involves a pair of variables
  - Higher-Order Constraints: Involves a 3 or more variables, can always be represented by multiple binary constraints.
  - Preferences (Soft Constraints): Could be presented by a cost for each assignments

The goal is to assign a value to each and every variable such that all constraints are satisfied.

CSP as a Search Problem

n variables X_1, X_2, \dots, X_n
Valid Assignment: \{X_{i1} \leftarrow v_{i1}, \dots, X_{ik} \leftarrow v_{ik}\}, k \in [0, n] such that the values satisfy all constraints relating the variables.
Complete Assignment: k = n
States: Valid assignments
Initial state: Empty assignment \{\}, i.e. k = 0
Successor of a state:\{X_{i1} \leftarrow v_{i1}, \dots, X_{ik} \leftarrow v_{ik}\} \rightarrow \{X_{i1} \leftarrow v_{i1}, \dots, X_{ik} \leftarrow v_{ik}, X_{ik+1} \leftarrow v_{ik+1}\}
Goal test: k = n

Commutativity of CSP

The order in which variables are assigned values has no impact on the reachable complete valid assignments.
Hence:

One can expand a node N by first selecting one variable X, which is not in the assignment A associated with N, and then assigning every value v in the domain of X, thus reduce the branching factor
One is not need to store the path to a node, allowing backtracking search algorithm.

CSP-Backtracking Algorithm

def CSP_backtracking(A: Assignment): Assignment
    if A.is_complete(): return A
    
    X = A.variables.not_set()
    D = X.domain.ordering()

    for v in D.values():
        A.assign(X, v)
        if A.is_valid():
            result = CSP_backtracking(A)
            if not result == Assignment.failedState(): return result
        A.unassign(X, v)

    return Assignment.FailedState()

CSP_backtracking(A = Assignment.EmptyAssignment())

Forward Checking

Forward Checking is a simple constraint-propagation technique.

  A.assign(X, v)    # After a pair is added to assignment...
+ for y in A.variables.not_set():
+     for c in A.constraints.get_related(y):
+        domain = y.domain
+        for val in domain.values():
+            if c.check_violate(val): domain.remove_value()
+ return domain

Modified Backtracking Algorithm

def CSP_backtracking(A: Assignment, var_domains: Domain): Assignment
    if A.is_complete(): return A
    
    X = A.variables.not_set()
    D = X.domain.ordering()

    for v in D.values():
        A.assign(X, v)
        # do inference here
        var_domains = forward_checking(var_domains, X, v, A)
        if count(var_domains.variables.empty_domain()) == 0:
            result = CSP_backtracking(A, var_domains)
            if not result == Assignment.failedState(): return result
        A.unassign(X, v)

    return Assignment.FailedState()

CSP_backtracking(A = Assignment.EmptyAssignment())

When selecting the next variable to assign, the most constrained variable should be chosen, if in a tie then the most constraining variable sould be chosen.

When selecting the values to assign, the least constaraining variable should be selected.

Constraint Propagation

Arc Consistency

An arc X \rightarrow Y is consistent if: \forall x \in X, \exist y such that y is consistent with x.

Arc consistency is capable of detect failures earlier than FC.

def arc_consistency_check(csp: CSProblem, xi : State, xj : State): bool
    # @returnValue False: arc inconsistency found
    # @returnValue True: arc inconsistency not found

    queue = [(xi, xj), (xj, xi)]
    
    while not queue.is_empty():
        checking_pair = queue.dequeue()
        if remove_inconsistent_values(checking_pair):
            if checking_pair[0].domain.size == 0: return False
            for xk in checking_pair[0]:
                if xk != checking_pair[1] and (xk, checking_pair[0]) not in queue: 
                    queue.enqueue((xk, checking_pair[0]))
    return True

def remove_inconsistent_values(xi, xj): bool
    removed = false
    for x in xi.domain:
        constraint_satisfy = False
        for y in xj.domain:
            constraint_check(variables = (xi, xj), values = (x, y))
        if constraint_satisfy == False: 
            xi.domain.remove(x)
            removed = True
    return removed

Local Search for CSPs

Local search algorithms can also be used for CSPs.

The idea is:

Use complete state representation allowing unsatisfied constraints
Operators reassign variable values
Selects conflicted variable to change
Reassign the variable with a value results in minimum number of conflicts

小毛龙

Lecture 07. Logical Agents

Knowledge and Reasoning

Logical Agents

Agents with some representation of the complex knowledge about the world and its environment, and uses inference to derive new information from that knowledge combined with new inputs.

Representation of knowledge -> Knowledge Base
- A set of sentences in a formal language representing facts (KR language)
Reasoning process -> inference/reasoning

Knowledge Bases

Knowledge base is a set of sentences in a formal language. It is a declarative approach to building an agent (or other system:

Tell it what it needs to know
Then it can Ask itself what to do - answers should follow from the KB
Agents can be viewed at the knowledge level or at the implementation level

Knowledge-based Agents

The agent must be able to:

Represent states, actions, etc.
Incorporate new percepts
Update internal representations of the world
Deduce hidden properties of the world
Deduce appropriate actions, etc.

Logic in General - Models and Entailment

Logic are formal languages for representing information such that conclusions can be drawn.
Syntax defines the sentences in the language.
Semantics define the "meaning" of sentences.
Entailment means that one thing follows from another: Entailment is a relationship between sentences (i.e., syntax) that is based on semantics.

Example: KB \models \alpha -> Knowledge base KB entails sentence \alpha if and
only if \alpha is true in all worlds where KB is true.

Models

A model of a set of sentences (KB) is a truth-assign in which each of the KB sentences evaluates to True.

Inference

If a sentence \alpha can be derived from KB by procedure i, we noteKB \vdash_i \alpha.

Soundness: i is sound if whenever KB \vdash_i \alpha, it is also true that KB \models \alpha.
Completeness: i is complete if whenever KB\models α, it is also true that KB \vdash_i \alpha.

Propositional (Boolean) Logic

Equivalence, Validity and Satisfiability

Two sentences are logically equivalent if and only if true in some models: \alpha \equiv \beta \text{iff} \alpha \models B \land \beta \models \alpha

A sentence is valid if it is true in ALL models. Validity is connected to inference via the Deduction Theorem:

KB \models \alpha text{iff} (KB \Rightarrow \alpha) is valid

A sentence is satisfiable if it is true in some models, and is unsatisfiable if it is true in NO models. Satisfiablity is connected to inference via:

KB \models \alpha text{iff} (KB \land \neg \alpha) is unsatisfiable

Inference Rules and Theorem Proving

Proof Methods

Application of inference rules
Model checking

Resolution

Conjunctive Normal Form (CNF)

CNF is conjuction of disjunctions of literals caluses.

Conversion Guide:

Eliminate A \Leftrightarrow B with (A \Rightarrow B)\land (B \Rightarrow A)

Eliminate A \Rightarrow B with (\neg A \lor B)

Move \neg inwards using de Morgan's rule (\neg (A \lor B) = \neg A \land \neg B) and double negation.

Apply distributivity law (\land over \lor) and flatten

Horn Clauses

A Horn clause is a clause with at most one positive literal.
Any Horn clause belongs to one of four categories:

A rule: 1 posotive literal, at least 1 negative literal.
- A rule has the form (\neg P1 \lor \neg P2 \lor \cdots \lor \neg Pk \lor Q), which is logically equivalent to (P1 \land P2 \land \cdots \land Pk \Rightarrow Q)
A fact or unit: 1 positive literal, 0 negative literals.
A negated goal: 0 positive literal, at least 1 negative literal.
- In almost all implementations of Horn clause logic, the negated goal is the negation of the statement to be proved.
The null clause: 0 positive and 0 negative literals. Appears only at the end of a resolution proof.

Forward Chaining

Backward Chaining

小毛龙

Lecture 08. First Order Logic

Whereas propositional logic assumes the world contains facts, first-order logic assumes the world contains:

Objects
Relations
Functions

The syntax of FOL contains:

Constants
Predicates
Functions
Variables
Connectives
Equality
Quantifiers

Atomic Sentences

An atomic sentence is a predicate of multiple terms, which may be function of terms, constants or variables.

Complex Sentences

Complex sentences are made from atomic sentences using connectives.